【範例】Tarjan algorithm
【題目敘述】https://tioj.ck.tp.edu.tw/problems/1683
【解題想法】Tarjan algorithm + Topological sort (拓撲排序)
- Tarjan algorithm：收縮所有的SCC (Strongly Connected Component, 強連通分量)，變成一張DAG (Directed Acyclic Graph, 有向無環圖)
- Topological sort (拓撲排序)：求最長路徑
#include <bits/stdc++.h>
using namespace std;
int t, n, m, a, b, instk[10005], dfn[10005], low[10005], idx;
int fa[10005], scc_sz[10005], in[10005], dp[10005], scc_cnt, mx;
vector <int> g[10005], g2[10005];
stack <int> stk;
void tarjan(int x){
instk[x] = 1;
stk.push(x);
dfn[x] = low[x] = ++idx;
for (int i:g[x]){
if (!dfn[i]){
tarjan(i);
low[x] = min(low[x], low[i]);
}
else if (instk[i]) low[x] = min(low[x], dfn[i]);
}
if (low[x] == dfn[x]){
scc_cnt++;
while (1){
int now = stk.top();
stk.pop();
fa[now] = scc_cnt;
scc_sz[scc_cnt]++;
instk[now] = 0;
if (now == x) break;
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--){
cin >> n >> m;
scc_cnt = 0;
idx = 0;
mx = 0;
for (int i = 1; i <= n; i++){
g[i].clear();
g2[i].clear();
dfn[i] = 0;
low[i] = 0;
fa[i] = 0;
scc_sz[i] = 0;
in[i] = 0;
dp[i] = 0;
}
for (int i = 0; i < m; i++){
cin >> a >> b;
g[a].push_back(b);
}
for (int i = 1; i <= n; i++){
if (!dfn[i]) tarjan(i);
}
for (int i = 1; i <= n; i++){
for (int j:g[i]){
if (fa[i] != fa[j]){
g2[fa[i]].push_back(fa[j]);
in[fa[j]]++;
}
}
}
queue <int> q;
for (int i = 1; i <= scc_cnt; i++){
//cout << i << " " << scc_sz[i] << " " << in[i] << "\n";
if (in[i] == 0) q.push(i);
}
while (!q.empty()){
int now = q.front();
q.pop();
dp[now] += scc_sz[now];
//cout << now << " " << dp[now] << "\n";
mx = max(mx, dp[now]);
for (int i:g2[now]){
dp[i] = max(dp[i], dp[now]);
in[i]--;
if (in[i] == 0) q.push(i);
}
}
cout << mx << "\n";
}
}