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

Resources | ||||
---|---|---|---|---|

CPH | ||||

Wikipedia |

### This section is not complete.

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_backconst 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 neighborstatic List<Integer>[] adj = new ArrayList[N + 1];// adjT is the transpose of adjstatic List<Integer>[] adjT = new ArrayList[N + 1];

## Tarjan's Algorithm

Resources | ||||
---|---|---|---|---|

CPC | ||||

CP2 | ||||

Wikipedia |

### This section is not complete.

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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsDP, SCC | |||

POI | Easy | ## Show TagsDP, SCC | |||

CF | Normal | ## Show TagsDP, SCC | |||

Old Gold | Normal | ## Show TagsSCC | |||

CF | Normal | ## Show TagsSCC | |||

CF | Hard | ## Show TagsSCC | |||

POI | Hard | ## Show TagsSCC | |||

Kattis | Hard | ## Show TagsSCC | |||

CSES | Very Hard | ## Show TagsSCC |

# 2-SAT

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:

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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Easy | ## Show Tags2SAT | |||

CF | Easy | ## Show Tags2SAT, DFS, DSU | |||

CC | Easy | ## Show Tags2SAT, DSU, Greedy, Sliding Window | |||

Kattis | Easy | ## Show Tags2SAT | |||

AC | Normal | ## Show Tags2SAT | |||

CF | Hard | ## Show Tags2SAT, Binary Search, Trees | |||

CF | Hard | ## Show Tags2SAT, DFS |

### Module Progress:

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