[BZOJ1654] [Usaco2006 Jan]The Cow Prom 奶牛舞会

本文主要是介绍[BZOJ1654] [Usaco2006 Jan]The Cow Prom 奶牛舞会，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=1654

题目大意

求图中包括点数大于1的强连通分量数

题解

模板测试

varw:array[0..70000,1..2]of longint;low,dfn,p,t:array[0..10005]of longint;i,j,k:longint;n,m,len,a,b,tmp,ans:longint;
procedure init(a,b:longint);
beginw[len,1]:=b;if w[a,2]=0then w[a,2]:=len else w[w[a,1],2]:=len;w[a,1]:=len; inc(len);
end;function min(a,b:longint):longint;
beginif a>b then exit(b) else exit(a);
end;procedure tarjan(a:longint);
var tt,s:longint;
begindfn[a]:=tmp; low[a]:=tmp; inc(tmp);inc(t[0]); t[t[0]]:=a; p[a]:=1;tt:=w[a,2];while tt<>0 dobeginif dfn[w[tt,1]]=0then begin tarjan(w[tt,1]); low[a]:=min(low[a],low[w[tt,1]]); endelse if p[w[tt,1]]=1 then low[a]:=min(low[a],dfn[w[tt,1]]);tt:=w[tt,2];end;s:=t[0];if dfn[a]=low[a] then beginrepeatp[t[t[0]]]:=0;dec(t[0]);until a=t[t[0]+1];if t[0]<>s-1 then inc(ans);end;
end;beginreadln(n,m); len:=n+1;for i:=1 to m dobegin readln(a,b); init(a,b); end;tmp:=1; ans:=0;for i:=1 to n doif dfn[i]=0 then tarjan(i);writeln(ans);
end.

这篇关于[BZOJ1654] [Usaco2006 Jan]The Cow Prom 奶牛舞会的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---