Strongly Connected Components (SCCs)

The definition of a kingdom in this problem is equivalent to the definition of a strongly connected component. We can compute these components using either Kosaraju's or Tarjan's algorithms, both of which are described below.

Kosaraju's Algorithm

Explanation

In the first phase, the algorithm performs a depth-first search (DFS) on the original graph to determine the exit times of vertices; that is, the node that is processed last will be at the top of the stack (reverse topological sort). As each vertex finishes processing, it is pushed onto a stack. In the next phase, nodes are processed off the stack in the order of their decreasing finish times. This ordering will be used in the second phase.

In the second phase, the algorithm conducts another DFS, this time on the transposed graph, where all edges are reversed. The DFS processes nodes according to the order defined by the stack from the first phase. By reversing the edges and following this specific order, each DFS run in this phase can identify all vertices of one SCC before moving on to the next.

We know that the transposed graph will have the same strongly connected components (SCCs) as the original because reversing an edge doesn't change the reachability within the components. Since each SCC is both maximal and disjoint. This means that within an SCC, every pair of vertices is mutually reachable; you can get from any vertex $u$ to any other vertex $v$, and vice versa. The term "maximal" indicates that you can't add any more vertices to an SCC without losing its strongly connected property. Furthermore, SCCs are disjoint, which means that no vertex can belong to more than one SCC. If a vertex were part of two SCCs, those SCCs would actually merge into a single, larger SCC. Therefore, reversing edges doesn't affect the undirected connections in the original graph.

During the second DFS, we process the vertices in the order determined by the stack from the first phase. This ensures that we start with the vertex that finished last in the initial DFS, which is guaranteed to be part of an SCC with no outgoing edges to other SCCs — essentially making it a "sink" in the transposed graph.

By processing the vertices in this specific order, we fully explore all vertices within the current SCC before moving on to the next one. SCCs are maximal subgraphs where every vertex can reach every other vertex within the same subgraph, so the DFS will traverse through all nodes in an SCC, isolating it completely. Once the entire SCC is processed, we move to the next highest exit time vertex that hasn’t been visited yet, ensuring that each SCC is handled independently and thoroughly, so no vertices from another SCC will be mistakenly included in the current one.

For visualization, refer to the TopCoder resource mentioned here.

Implementation

Time Complexity: $\mathcal{O}(N+M)$

Copy
order = []


def dfs1(v: int):
	"""Calculate the order to process nodes."""
	stack = [v]
	while stack:
		node = stack[-1]
		if not vis[node]:
			vis[node] = True

Tarjan's Algorithm

Explanation

In Tarjan's algorithm, a single depth-first search (DFS) is performed on the original graph to determine the discovery times and the lowest reachable nodes (low values) for each vertex; that is, the node that is discovered first in a cycle acts as the anchor. As each vertex is visited for the first time, it is pushed onto a stack. An important stack invariant maintained during this process is that each vertex in the stack has a path to the following vertex in the stack. In this single phase, nodes are processed and kept on the stack as long as they are part of the current active search path. This stack will be used to extract the components.

During this DFS, the algorithm explores all outgoing edges from the current vertex, updating its low value to track the lowest discovery time reachable specifically among nodes that are still active on the stack. The DFS processes nodes according to the edges defined by the original graph. By tracking discovery times and following this specific order, the DFS run can identify all vertices of one SCC before extracting them and moving on to the next.

We know that identifying cycles using discovery times will find the exact same strongly connected components (SCCs) because tracking lowest reachable nodes perfectly maps the reachability within the components. Each SCC is both maximal and disjoint. This means that within an SCC, every pair of vertices is mutually reachable; you can get from any vertex $u$ to any other vertex $v$, and vice versa. The term "maximal" indicates that you can't add any more vertices to an SCC without losing its strongly connected property. Furthermore, SCCs are disjoint, which means that no vertex can belong to more than one SCC. If a vertex were part of two SCCs, those SCCs would actually merge into a single, larger SCC. Therefore, ignoring cross-edges to nodes already removed from the stack doesn't affect the valid connections in the current graph.

After fully exploring all neighbors of a vertex, we check if the vertex's low value still exactly matches its original discovery identifier. This ensures that we identify the node that was discovered first in the current cycle, which is guaranteed to be part of an SCC with no paths looping back to earlier discovered SCCs — essentially making it a root in the DFS spanning tree.

By processing the vertices in this specific order, we fully explore all vertices within the current SCC before extracting it. SCCs are maximal subgraphs where every vertex can reach every other vertex within the same subgraph, so the DFS will traverse through all nodes in an SCC, stacking them consecutively above the root. Once the entire SCC is processed and the root is identified, we pop nodes off the stack until the root is removed, ensuring that each SCC is handled independently and thoroughly, so no vertices from another SCC will be mistakenly included in the current one.

Implementation

Time Complexity: $\mathcal{O}(N+M)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::min;
using std::vector;

/** Takes in an adjacency list and calculates the SCCs of the graph. */

Problems

2-SAT

Explanation

Introduction

The CSES problem already gives us a boolean formula in conjunctive normal form (CNF) that consists of a series of logical OR clauses ANDed together like so:

Before we proceed, try linking this to graph theory. Hint: represent a variable and its negation with two nodes.

Construction

Like the hint says, we can construct a graph with each variable having two nodes: one for itself and one for its negation. We're going to try to proceed by assigning each node a truth value. Note that the value of one of the variable's nodes determines the other, since if we know the value of one node, the other is the negation of that value.

Now, for each clause $(a \lor b)$, we add two directed edges: $\lnot a \rightarrow b$ and $\lnot b \rightarrow a$. What this means for us is that if $a$ was false, then $b$ must be true, and vice versa.

With these edges, an SCC implies a group of values that all have to have the same truth value.

Solving the Graph

The only way for there to be an impossible assignment of truth values is if a node and its negation are in the same SCC, since this means that a boolean and its negation have to both be true, which is impossible.

If the graph is consistent and there are no impossible configurations, we can start assigning truth values, starting from the SCCs that have no outgoing edges to other SCCs and proceeding backwards. With the initial SCCs, we set them all to true. As for other SCCs, if a value has already been assigned due to its negation being in a previously processed component, we have to assign all other values in the component to that value.

Due to certain properties about the graph we've constructed, we can guarantee that the resulting assignment of the variables does not have any "true" SCCs leading to "false" SCCs. A proof of this is beyond the scope of this module.

Implementation

We use Tarjan's algorithm as it already provides us with a topological order to process the nodes in. However, it is also possible to use Kosaraju's algorithm.

Time Complexity: $\mathcal{O}(N+M)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

 Code Snippet: SCC Solver (Click to expand)

Problems