算法討論：這題陷阱比較多。首先，被所有牛歡迎，這說明所有的牛都要在一個連通圖中，也就是將所給的邊看成無向邊的時候，所有點要在一個連通圖中。這個我們用并查集來實現(xiàn)就可以了。強連通分量的求法就很簡單了，正常的Tarjan就好了。求完強連通分量之后重新建圖，找出新圖上出度為0的點，那么在原圖上在這個強連通分量中的點的個數(shù)就是答案。

我的代碼：

program popular;//By_Thispoet constmaxn=10005; vari,j,k,m,n,p,q,total,time,size :longint;pr,la,ot,pre,other,last :array[0..maxn*5]of longint;stack,father :array[0..maxn]of longint;color,dfn,low,num :array[0..maxn]of longint;outo :array[0..maxn]of longint;function min(i,j:longint):longint; beginif i<j then exit(i);exit(j); end;function root(i:longint):longint; beginif father[i]=i then exit(i);father[i]:=root(father[i]);exit(father[i]); end;procedure union(i,j:longint); var x,y:longint; beginx:=root(i);y:=root(j);father[x]:=y; end;procedure deal(i:longint); begininc(total);while stack[size]<>i dobegincolor[stack[size]]:=total;inc(num[total]);dec(size);end;color[i]:=total;inc(num[total]);dec(size); end;procedure tarjan(i:longint); var j,k:longint; begininc(time);dfn[i]:=time;low[i]:=time;inc(size);stack[size]:=i;j:=la[i];while j<>0 dobegink:=ot[j];if dfn[k]<>-1 thenlow[i]:=min(low[i],dfn[k]) elsebegintarjan(k);low[i]:=min(low[i],low[k]);end;j:=pr[j];end;if low[i]=dfn[i] then deal(i); end;procedure prepare; begink:=0;for i:=1 to n do beginj:=la[i];p:=color[i];while j<>0 do beginq:=color[ot[j]];if p<>q then inc(outo[p]);j:=pr[j];end;end; end;beginreadln(n,m);fillchar(num,sizeof(num),0);fillchar(la,sizeof(la),0);for i:=1 to n do father[i]:=i;for i:=1 to m dobeginreadln(p,q);union(p,q);inc(k);pr[k]:=la[p];la[p]:=k;ot[k]:=q;end;for i:=1 to n do if root(i)<>root(1) then beginwriteln(0);halt;end;fillchar(dfn,sizeof(dfn),255);for i:=1 to n doif dfn[i]=-1 then tarjan(i);prepare;p:=0;q:=0;for i:=1 to total do if outo[i]=0 thenbegininc(p);q:=i;end;if p=1 then writeln(num[q]) else writeln(0); end.

轉(zhuǎn)載于:https://www.cnblogs.com/Thispoet/archive/2011/10/18/2216623.html

總結(jié)

以上是生活随笔為你收集整理的POJ2186——并查集+Tarjan算法求强连通分量的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。