2012-08-28 09:40:15Morris
[ZJ][scc強連通元件][Tarjan算法] b201. F. 國家
內容 ：
傳說在遙遠的古代，整個地球的大陸是一整塊，整塊大陸上有n 個城市。這些城市間有共有m
條道路相連接，不過有趣的是這些道路只能夠單向通行。有一天上帝決定把整塊大陸切成幾塊形成各自的國家。分割的策略就是把原本就可以互相聯絡的幾個城市當
成一個國家（如果有一條路徑從城市i 到城市j 且有一條路徑從城市j 到城市i，則城市i 和城市j
就在同一個國家）。上帝想請你幫一個忙，他想知道每個國家的大小。也就是每個國家到底包含了幾個城市。
以下是一個簡單的例子：
如果有一條單行道從城市 i 接到城市j 用(i,j)表示如果一開始有 3 個城市，然後有3 條單行道(1, 2), (2, 1), (2, 3) 則可以分成兩個國家，分別包含了2 個城市(1, 2)和1 個城市(3)。
以下是一個簡單的例子：
如果有一條單行道從城市 i 接到城市j 用(i,j)表示如果一開始有 3 個城市，然後有3 條單行道(1, 2), (2, 1), (2, 3) 則可以分成兩個國家，分別包含了2 個城市(1, 2)和1 個城市(3)。
輸入說明
：
輸入檔中會有多筆資料，每一組資料的第一行第一行包
含了城市數量 n(1<=n<=100000)和單行道的數量m(1<=m<=2100000)，接下來m
行，每一行中都包含兩個數字i, j 代表有一條單行道從城市i 連到城市j(注意兩個城市間可能有不只兩條的單行道)。
輸出說明
：
對於每一組資料輸出一行，內容是排序過後每個國家的大小。
範例輸入 ：
3 3 1 2 2 1 2 3 2 2 1 2 2 1
範例輸出 ：
1 2 2
提示
：
出處
：
2008 NPSC 高中組初賽
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define maxN 100010
using namespace std;
vector<int> g[maxN];
int stk[maxN], stkIdx;
int visited[maxN], in_stk[maxN];
int vfind[maxN], findIdx;
int lead[maxN];
int group[maxN], gIdx;
int scc(int nd) {
visited[nd] = in_stk[nd] = 1;
stk[++stkIdx] = nd;
vfind[nd] = ++findIdx;
int mn = vfind[nd];
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(!visited[*it]) {
mn = min(mn, scc(*it));
}
if(in_stk[*it]) {
mn = min(mn, vfind[*it]);
}
}
if(mn == vfind[nd]) {
int cnt = 0;
do {
cnt++;
lead[stk[stkIdx]] = nd;
in_stk[stk[stkIdx]] = 0;
} while(stk[stkIdx--] != nd);
group[++gIdx] = cnt;
}
return mn;
}
int main() {
int n, m, x, y;
int i;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 1; i <= n; i++) {
g[i].clear();
vfind[i] = visited[i] = in_stk[i] = 0;
lead[i] = i;
}
while(m--) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
}
gIdx = -1;
for(i = 1; i <= n; i++) {
if(!visited[i]) {
findIdx = 0, stkIdx = -1;
scc(i);
}
}
sort(group, group+gIdx+1);
printf("%d", group[0]);
for(i = 1; i <= gIdx; i++)
printf(" %d", group[i]);
puts("");
}
return 0;
}
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define maxN 100010
using namespace std;
vector<int> g[maxN];
int stk[maxN], stkIdx;
int visited[maxN], in_stk[maxN];
int vfind[maxN], findIdx;
int lead[maxN];
int group[maxN], gIdx;
int scc(int nd) {
visited[nd] = in_stk[nd] = 1;
stk[++stkIdx] = nd;
vfind[nd] = ++findIdx;
int mn = vfind[nd];
for(vector<int>::iterator it = g[nd].begin();
it != g[nd].end(); it++) {
if(!visited[*it]) {
mn = min(mn, scc(*it));
}
if(in_stk[*it]) {
mn = min(mn, vfind[*it]);
}
}
if(mn == vfind[nd]) {
int cnt = 0;
do {
cnt++;
lead[stk[stkIdx]] = nd;
in_stk[stk[stkIdx]] = 0;
} while(stk[stkIdx--] != nd);
group[++gIdx] = cnt;
}
return mn;
}
int main() {
int n, m, x, y;
int i;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 1; i <= n; i++) {
g[i].clear();
vfind[i] = visited[i] = in_stk[i] = 0;
lead[i] = i;
}
while(m--) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
}
gIdx = -1;
for(i = 1; i <= n; i++) {
if(!visited[i]) {
findIdx = 0, stkIdx = -1;
scc(i);
}
}
sort(group, group+gIdx+1);
printf("%d", group[0]);
for(i = 1; i <= gIdx; i++)
printf(" %d", group[i]);
puts("");
}
return 0;
}