BZOJ

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.