poj 2186/Bzoj 1051(Tarjan强连通分量)

poj 2186
Bzoj 1051
这题求所有满足被所有点能够到达的节点,那么我们可以进行缩点,缩点之后得到一个有向DAG图,统计新图的出度,如果有一个强连通分量的出度是=0的,那么输出这个强连通分量的大小,如果有多个,输出0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#define ms(i ,j) memset(i, j, sizeof i)
#define rd2(a, b) scanf("%d%d", &a, &b)
#define rd3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define FN2 "poj2186"
using namespace std;
const int MAXN = 10000 + 5;
int n,m;
vector<int> G[MAXN];
int cnt, scc_size[MAXN], scc_out[MAXN], scc_belong[MAXN];
int tb, dn[MAXN], low[MAXN], ex[MAXN];
stack<int> s;
void tarjan(int u)
{
dn[u] = low[u] = ++tb;
ex[u] = -1; s.push(u);
for (int i=0;i<G[u].size();i++)
{
int v = G[u][i];
if (ex[v]==0)
{
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (ex[v]==-1)
{
low[u] = min(low[u], dn[v]);
}
}
if (dn[u]==low[u])
{
cnt++;
int e;
do
{
e = s.top(); s.pop();
scc_belong[e] = cnt;
scc_size[cnt]++;
ex[e] = 1;
}while (e!=u);
}
}
void rebuild()
{
for (int x=1;x<=n;x++)
{
for (int i=0;i<G[x].size();i++)
{
int v = G[x][i];
if (scc_belong[x]!=scc_belong[v])
{
scc_out[scc_belong[x]]++;
break;
}
}
}
}
void init()
{
for (int i=1;i<=m;i++)
{
int a,b; rd2(a, b);
G[a].push_back(b);
}
cnt = tb = 0; ms(ex, 0); ms(scc_size, 0); ms(scc_out, 0);
}
void solve()
{
for (int i=1;i<=n;i++)
if (!dn[i]) tarjan(i);
rebuild();
int tot = 0, ans = 0;
for (int i=1;i<=cnt;i++)
if (scc_out[i]==0)
{
tot++; ans = scc_size[i];
if (tot>=2)
{
ans = 0;
break;
}
}
printf("%d\n", ans);
}
int main()
{
while (rd2(n,m)==2)
{
init();
solve();
}
fclose(stdin); fclose(stdout);
return 0;
}

------ 本文结束 ------