POJ2186——并查集+Tarjan算法求强连通分量

算法讨论：这题陷阱比较多。首先，被所有牛欢迎，这说明所有的牛都要在一个连通图中，也就是将所给的边看成无向边的时候，所有点要在一个连通图中。这个我们用并查集来实现就可以了。强连通分量的求法就很简单了，正常的Tarjan就好了。求完强连通分量之后重新建图，找出新图上出度为0的点，那么在原图上在这个强连通分量中的点的个数就是答案。

我的代码：

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.

转载于:https://www.cnblogs.com/Thispoet/archive/2011/10/18/2216623.html

总结

以上是生活随笔为你收集整理的POJ2186——并查集+Tarjan算法求强连通分量的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。