Planets and Kingdoms

Problem Overview

Learning Goals

After solving this problem, you will understand:

1. Practical SCC Application: How SCC theory translates to real problem solving
2. Component Labeling: How to assign unique IDs to each component
3. Output Formatting: Returning per-node component membership

Problem Statement

A game has n planets (numbered 1 to n) and m one-way teleporters. You need to divide the planets into kingdoms such that:

• You can travel between any two planets in the same kingdom (using teleporters)
• This is the definition of a Strongly Connected Component (SCC)

Output Format:

1. First line: k = number of kingdoms
2. Second line: n integers where the i-th integer is the kingdom number of planet i

Example:

Input:
5 6
1 2
2 3
3 1
1 4
4 5
5 4

Output:
2
1 1 1 2 2

Explanation: Planets {1,2,3} form one kingdom (they have a cycle 1->2->3->1), and planets {4,5} form another kingdom (cycle 4->5->4). Total: 2 kingdoms.

Key Insight: Direct SCC Application

This problem is a direct application of finding Strongly Connected Components:

Kingdom = Strongly Connected Component

Why? A kingdom groups planets where you can travel between ANY two planets.
This is exactly the definition of an SCC in a directed graph.

The Algorithm:

1. Run Kosaraju’s algorithm to find all SCCs
2. During pass 2, assign each node its component number
3. Output: count of components + component ID for each node

Algorithm: Kosaraju’s with Component Labeling

For a detailed explanation of Kosaraju’s algorithm, see Strongly Connected Components Analysis.

Key Modification: We need to track which component each node belongs to.

Standard Kosaraju:           This Problem:
- Find all SCCs              - Find all SCCs
- Return list of SCCs        - Return component[i] for each node i

Visual Diagram

Original Graph:                  Kingdoms Found:
    1 --> 2                      Kingdom 1: {1, 2, 3}
    ^     |                      Kingdom 2: {4, 5}
    |     v
    3 <---+                      Component Assignment:
    |                            Planet 1 -> Kingdom 1
    v                            Planet 2 -> Kingdom 1
    4 <--> 5                     Planet 3 -> Kingdom 1
                                 Planet 4 -> Kingdom 2
                                 Planet 5 -> Kingdom 2

Dry Run

Input: n=5, m=6, Edges: (1,2), (2,3), (3,1), (3,4), (4,5), (5,4)

Step 1: Build graphs
Original adj[]:          Reversed adj[]:
1: [2]                   1: [3]
2: [3]                   2: [1]
3: [1, 4]                3: [2]
4: [5]                   4: [3, 5]
5: [4]                   5: [4]

Step 2: First DFS (finish order)
Visit: 1 -> 2 -> 3 -> 4 -> 5
Finish order: [5, 4, 3, 2, 1]

Step 3: Second DFS on reversed graph (reverse finish order)
Process 1: DFS finds {1, 3, 2} -> Kingdom 1
Process 4: DFS finds {4, 5}    -> Kingdom 2

Result: 2 kingdoms, assignments: [1, 1, 1, 2, 2]

Python Implementation

import sys
from collections import defaultdict
sys.setrecursionlimit(200001)

def solve():
  n, m = map(int, input().split())

  # Build adjacency lists (1-indexed)
  adj = defaultdict(list)      # Original graph
  radj = defaultdict(list)     # Reversed graph

  for _ in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    radj[b].append(a)

  # Pass 1: DFS on original graph to get finish order
  visited = [False] * (n + 1)
  order = []

  def dfs1(u):
    visited[u] = True
    for v in adj[u]:
      if not visited[v]:
        dfs1(v)
    order.append(u)

  for i in range(1, n + 1):
    if not visited[i]:
      dfs1(i)

  # Pass 2: DFS on reversed graph, assign component IDs
  visited = [False] * (n + 1)
  component = [0] * (n + 1)
  comp_id = 0

  def dfs2(u, cid):
    visited[u] = True
    component[u] = cid
    for v in radj[u]:
      if not visited[v]:
        dfs2(v, cid)

  # Process in reverse finish order
  for u in reversed(order):
    if not visited[u]:
      comp_id += 1
      dfs2(u, comp_id)

  # Output
  print(comp_id)
  print(' '.join(map(str, component[1:])))

solve()

Connection to SCC Problem

What’s Different?

• SCC problem: Return [[1,2,3], [4,5]]
• This problem: Return k=2 and [1,1,1,2,2]

The modification is minimal - just track the component ID during pass 2.

Common Mistakes

Complexity Analysis

Related Problems

• CSES: Strongly Connected Components - Find SCCs
• CSES: Giant Pizza - 2-SAT using SCCs
• CSES: Coin Collector - DP on SCC DAG