Rare
0/11
Strongly Connected Components
Authors: Benjamin Qi, Dong Liu, Neo Wang
Subsets of nodes in directed graphs where each node in a subset can reach each other node in the subset.
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 |
Solution (Kosaraju's)
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 |
Solution (Tarjan's)
C++
#include <bits/stdc++.h>using namespace std;/*** Description: Tarjan's, DFS once to generate* strongly connected components in topological order. $a,b$* in same component if both $a\to b$ and $b\to a$ exist.* Uses less memory than Kosaraju b/c doesn't store reverse edges.* Time: O(N+M)* Source: KACTL* https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/SCC.h
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!
This section is not complete.
Any help would be appreciated! Just submit a Pull Request on Github.
implementation
Tutorial
This section is not complete.
Any help would be appreciated! Just submit a Pull Request on Github.
mention KACTL - at most one
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!