題意#
一個宇宙中有 \(n\) 顆星球，以及 \(m\) 條單向的「傳送門」連接著它們。如果星球 A 可以透過傳送門走到星球 B，而且星球 B 也能走得回星球 A，我們就稱這兩顆星球屬於同一個「王國」。
你的任務是計算出這個宇宙中總共有幾個王國？並順便標記出每顆星球分別隸屬於哪個王國（王國編號從 1 到 \(k\) 自由分配即可）。
思路#
這題的定義非常清楚，能「互相抵達」的一群節點就是一個王國。在圖論中，這群節點有著一個專有名詞，叫做「強連通分量（Strongly Connected Components, SCC）」。簡而言之，這是一道求解有向圖 SCC 的經典題。
要找出圖中所有的 SCC，最多人愛用的莫過於 Kosaraju’s Algorithm，它的實作非常優雅，僅需利用兩次 DFS 與正反兩張圖就能搞定：
- 第一次 DFS（原圖）：我們在原本的圖上隨意點擊未走過的節點進行深搜。這裡的重點不是要直接分出王國，而是每當一個節點「所有往下延伸的子節點都走完了，準備從 DFS 抽身（離開）」時，我們就把這個節點推進一個堆疊（Stack）裡存起來。這一步的精神是：越容易走到別人卻回不來的節點（像是無尾巷），它會越早被結束深搜並壓在堆疊底下；而最不容易出去的「源頭」，反而會最後才離開 DFS 並留在堆疊最上方。
- 第二次 DFS（反向圖）：有了堆疊後，我們把整張圖的連線方向顛倒（反向圖）。接著不斷從堆疊頂端拿出節點，只要它還沒被分派過王國，我們就把他當作新的國王，從他開始在反向圖上深搜。能夠在這個階段被 DFS 一次掃到的所有節點，保證跟這個國王屬於同一個 SCC！
最後，我們只要統計總共發起了幾次深搜，就是王國的總數，而在第二次 DFS 順手標記上的變數，就是每顆星球的王國歸屬證明。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
// g: 原圖, gr: 反向圖（Reverse Graph）
vector<vector<int>> g, gr;
vector<int> vis; // 用於標記走訪狀態或王國編號
stack<int> order; // 記錄第一次 DFS 的離開順序
int t, ck;
// 第一階段的 DFS：遍歷原圖，並將抵達終結點（無法再深入）的節點壓入堆疊
void dfs1(int x) {
vis[x] = 1; // 標記為已造訪
for (auto u : g[x]) if (!vis[u]) {
vis[u] = 1;
dfs1(u); // 繼續往深處挖
}
// 所有相鄰節點都巡完了，準備離開此節點，將其推入堆疊
order.push(x);
}
// 第二階段的 DFS：在反向圖上根據堆疊順序探索，能一次走完的點即為同一個 SCC
void dfs2(int x) {
vis[x] = t; // 將該星球標記為第 t 個王國
for (auto u : gr[x]) if (!vis[u]) {
dfs2(u); // 沿著反向邊把同屬一個王國的人通通找出來
}
}
signed main() { WA();
int n, m; cin >> n >> m;
g.assign(n+1, vector<int>());
gr.assign(n+1, vector<int>());
// 建立正向圖與反向圖
while (m--) {
int a, b; cin >> a >> b;
g[a].pb(b); // 正向邊 a -> b
gr[b].pb(a); // 反向邊 b -> a
}
// ----- Step 1: 原圖 DFS 蒐集離開順序 -----
vis.assign(n+1, 0);
// 確保即使圖不連通，每一顆星球都能被探索到
for (int i = 1; i <= n; i++) if (!vis[i]) {
dfs1(i);
}
// ----- Step 2: 反向圖 DFS 分配王國 -----
t = 1, ck = 0;
int cnt = 0; // 王國總數計數器
vis.assign(n+1, 0); // 清空陣列，準備用來記錄每個人最終的王國編號
// 依照離開順序的倒置（堆疊頂端，也就是最早進去的源頭）開始搜索
while (order.size()) {
if (!vis[order.top()]) { // 如果這顆星球還沒被歸化
dfs2(order.top()); // 建立一個新王國，並把成員都抓齊
t++; // 為下一個潛在王國準備新編號
cnt++; // 王國總數加一
}
order.pop(); // 看完就丟掉
}
// 整理輸出格式：先砍掉索引 0 的空位，然後印出王國數與各星球的國籍
vis.erase(vis.begin());
cout << cnt << '\n';
// \n[&i == &vis.back()] 是一種精緻的 C++ 技巧，只有印到最後一項時才換行
for (auto &i : vis) cout << i << " \n"[&i == &vis.back()];
}
