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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10000;
int low[N], stack[N],head[N],top,cnt,color[N],dfn[N],num,in[N],out[N],indexx;
bool instack[N];
struct
{
int next, v;
}node[N];
void add(int u,int v)
{
node[++cnt].next = head[u];
node[cnt].v = v;
head[u] = cnt;
return;
}
void tarjan(int u)
{
low[u]=dfn[u]=++indexx;
stack[++top] = u;
instack[u] = 1;
for (int i = head[u]; i;i=node[i].next)
{
int v = node[i].v;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(instack[v])
low[u] = min(low[u], dfn[v]);
}
if(dfn[u]==low[u])
{
num++;
do
{
color[stack[top]] = num;
instack[stack[top]] = false;
} while (stack[top--] != u);
}
return;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n;i++)
{
int a;
while(cin>>a&&a)
{
add(i, a);
}
}
for (int i = 1; i <= n;i++)
{
if(!dfn[i])
tarjan(i);
}
for (int i = 1; i <= n;i++)
{
for (int j = head[i]; j;j=node[j].next)
{
if(color[i]!=color[node[j].v])
{
out[color[i]]++;
in[color[node[j].v]]++;
}
}
}
int inc = 0, outc = 0;
for(int i = 1;i <= num;i ++) {
inc += in[i] == 0 ? 1 : 0;
outc += out[i] == 0 ? 1 : 0;
}
if(num == 1) cout << "1n0" << endl;
else cout << inc << endl << max(inc, outc) << endl;
}
|
近期评论