CSES - Planets and Kingdoms

Author: Dong Liu

Edit This Page

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

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

Then assign each component an IDID (starting from 11).

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!

Join Forum