poj 1236(Tarjan强连通分量)

poj 1236

tarjan

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "poj1236"
using namespace std;
const int MAXN = 100 + 5;
vector<int> G[MAXN];
stack<int> s;
int n, low[MAXN], dn[MAXN], tb, ex[MAXN];
int cnt, scc_out[MAXN], scc_in[MAXN], scc_belong[MAXN];
void tarjan(int u)
{
low[u] = dn[u] = ++tb;
s.push(u), ex[u] = -1;
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 (low[u]==dn[u])
{
int e;
cnt++;
do
{
e = s.top(); s.pop();
scc_belong[e] = cnt;
ex[e] = 1;
} while (u!=e);
}
}
void rebuild()
{
for (int u=1;u<=n;u++)
{
for (int i=0;i<G[u].size();i++)
{
int v = G[u][i];
if (scc_belong[u]!=scc_belong[v])
{
scc_out[scc_belong[u]] = 1;
scc_in[scc_belong[v]] = 1;
}
}
}
}
void init()
{
for (int i=1;i<=n;i++)
{
low[i] = dn[i] = ex[i] = scc_out[i] = scc_in[i] = scc_belong[i] = 0;
G[i].clear();
}
tb = cnt = 0;
for (int i=1;i<=n;i++)
{
int x;
while (scanf("%d", &x)==1&&x)
{
G[i].push_back(x);
}
}
}
void solve()
{
for (int i=1;i<=n;i++)
if (!dn[i]) tarjan(i);
rebuild();
int ans = 0, ansin = 0, ansout = 0;
for (int i=1;i<=cnt;i++) if (!scc_in[i]) ansin++;
for (int i=1;i<=cnt;i++) if (!scc_out[i]) ansout++;
ans = max(ansin, ansout);
if (cnt==1) printf("1\n0\n"); else printf("%d\n%d\n", ansin, ans);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen(FN2".in","r",stdin);
freopen(FN2".out","w",stdout);
#endif
while (scanf("%d", &n)==1)
{
init();
solve();
}
return 0;
}

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