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
#include <bits/stdc++.h>

const int N = 1e5 + 1;

// adj_t is the transpose of adj
std::vector<int> adj[N], adj_t[N];
std::vector<int> order;
std::vector<int> vis(N), id(N);

// calculates the order in which nodes are processed

Copy
import java.io.*;
import java.util.*;

public class Main {
	static final int N = 100001;
	static boolean[] vis = new boolean[N + 1];
	// Adjacency list of neighbor
	static List<Integer>[] adj = new ArrayList[N + 1];
	// adjT is the transpose of adj
	static List<Integer>[] adjT = new ArrayList[N + 1];

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

Implementation

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

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

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

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

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