Rare
0/18

# Strongly Connected Components

Authors: Benjamin Qi, Dong Liu, Neo Wang, Rameez Parwez

Subsets of nodes in directed graphs where each node in a subset can reach each other node in the subset.

# Strongly Connected Components (SCCs)

Focus Problem – try your best to solve this problem before continuing!

View Internal Solution

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

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on GitHub.

in-house explanation?

## Implementation

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

C++

#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 adjvi adj[mx], adj_t[mx], S;

Java

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];

## Tarjan's Algorithm

### This section is not complete.

Any help would be appreciated! Just submit a Pull Request on GitHub.

link to dpv in resources and just tell them to look at that, no way we're beating that explanation

## Implementation

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

C++

#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

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsDP, SCC
POIEasy
Show TagsDP, SCC
CFNormal
Show TagsDP, SCC
Old GoldNormal
Show TagsSCC
CFNormal
Show TagsSCC
CFHard
Show TagsSCC
POIHard
Show TagsSCC
KattisHard
Show TagsSCC
CSESVery Hard
Show TagsSCC

# 2-SAT

Resources
CF
cp-algo
Algorithms Live!

Focus Problem – try your best to solve this problem before continuing!

## 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:

$(\lnot x_1 \lor x_2) \land (x_1 \lor \lnot x_2) \land (\lnot x_1 \lor \lnot x_2) \land (x_1 \lor \lnot x_3)$

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)$

C++

#include <algorithm>#include <iostream>#include <vector>
using std::cout;using std::endl;using std::vector;
Code Snippet: SCC Solver (Click to expand)


## Problems

StatusSourceProblem NameDifficultyTags
CFEasy
Show Tags2SAT
CFEasy
Show Tags2SAT, DFS, DSU
CCEasy
Show Tags2SAT, DSU, Greedy, Sliding Window
KattisEasy
Show Tags2SAT
ACNormal
Show Tags2SAT
CFHard
Show Tags2SAT, Binary Search, Trees
CFHard
Show Tags2SAT, DFS

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!