CSES - Planets and Kingdoms
Author: Dong Liu
Time Complexity:
Just run Kosaraju's or Tarjan's SCC algorithm on the graph.
Then assign each component an (starting from ).
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!