BZOJ 1051

强连通分量模板题

传送门

注意是单向边

拿裸的${\rm Tarjan}$缩点,然后统计每个强连通分量的出度和大小

假设有俩强连通分量$A$和$B$,$A_2$认识$B_1$,那么$A_1$就一定认识$B_2$,因为强连通分量内一定两两可达嘛,所以只要两个强连通分量间有$A\rightarrow B$的边,那么所有$A$一定认识所有$B$

对于每个强连通分量,若其出度为${\rm 0}$则说明里面的任一头牛都不认识外面的,但外面的可能认识里面的

若有多个出度为${\rm 0}$的强连通分量,说明肯定有牛互相不认识,那不就不满足题意了嘛…

所以若出度为${\rm 0}$的强连通分量只有一个,则输出它的大小,否则输出${\rm 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
program bzoj_1051;
var low,dfn,lst,cnt,s,bl:array[0..10000]of longint;
l:array[1..100000]of record ed,pre:longint; end;
v,ins,noout:array[0..10000]of boolean;
n,m,scc,tot,i,a,b,time,top,ans:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure link(a,b:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
end;
procedure dfs(t:longint);
var k:longint;
begin
inc(time);
low[t]:=time;
dfn[t]:=time;
v[t]:=true;
ins[t]:=true;
inc(top);
s[top]:=t;
k:=lst[t];
while k<>0 do
begin
if not v[l[k].ed] then
begin
dfs(l[k].ed);
low[t]:=min(low[t],low[l[k].ed]);
end else if ins[l[k].ed] then low[t]:=min(low[t],dfn[l[k].ed]);
k:=l[k].pre;
end;
if dfn[t]=low[t] then
begin
inc(scc);
repeat
inc(cnt[scc]);
bl[s[top]]:=scc;
ins[s[top]]:=false;
dec(top);
until s[top+1]=t;
end;
end;
procedure rebuild;
var i,k:longint;
begin
fillchar(noout,sizeof(noout),true);
for i:=1 to n do
begin
k:=lst[i];
while k<>0 do
begin
if bl[i]<>bl[l[k].ed] then noout[bl[i]]:=false;
k:=l[k].pre;
end;
end;
end;
begin
readln(n,m);
tot:=0;
for i:=1 to m do
begin
readln(a,b);
link(a,b);
end;
fillchar(v,sizeof(v),0);
fillchar(cnt,sizeof(cnt),0);
top:=0;
scc:=0;
for i:=1 to n do if not v[i] then dfs(i);
rebuild;
ans:=0;
for i:=1 to scc do if noout[i] then
if ans<>0 then
begin
writeln(0);
halt;
end else ans:=cnt[i];
writeln(ans);
end.