# CSES - Planets and Kingdoms

Author: Dong Liu

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

Just run Kosaraju's or Tarjan's SCC algorithm on the graph.

Then assign each component an $ID$ (starting from $1$).

### With Kosaraju's SCC:

C++

#include <bits/stdc++.h>using namespace std;/*** Description: Kosaraju's Algorithm, DFS twice to generate* strongly connected components in topological order. $a,b$* in same component if both $a\to b$ and $b\to a$ exist.* Time: O(N+M)* Source: Wikipedia* Verification: POI 8 peaceful commission

### With Tarjan's SCC

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

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