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

Implementation

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

Copy
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
#define pb push_back

const int mx = 1e5 + 1;

// adj_t is the transpose of adj
vi adj[mx], adj_t[mx], S;

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