POJ - 2186 Tarjan的模板题..

POJ - 2186 Tarjan的模板题..

暑假的时候研究过kosaraju~~A过一些强连通分量..Kosaraju需要做两个图, 一个原图一个是原图的反图(每个边的终点起点反过来..)..正着DFS一次...标记出栈顺序..再根据这个出栈顺序对反图进行一次DFS..每次能遍历到的点就是在一起的强连通分量...

Tarjan同样是用的对图DFS...Byvoid大牛的这个文章很适合初学者​​= DFN 的点为止..

4、弹栈时注意instack,也就是标记点是不是在栈中的要跟着更新...

5、可能有的点完全孤立..就是根本没有边...所以做完Tarjin后..检查所有的点是不是都处理过了..如果有没处理的...直接返回没有大牛( 0 )..

这道题是要找所有人都能仰慕到的...也就是除了自己的所有强连通分量里都能到自己的强连通分量就是一个大牛集合...这里在做完Tarjan后...要先进行缩点..就是把每个强连通分量都缩成一个点..然后再来判断...

Program::

//POJ2186 找大牛 Tarjin#include#include#include#define MAXN 15001using namespace std;struct pp{ int x,y,next; }line[MAXN*5],line2[MAXN*5];int n,m,link[MAXN],tp[MAXN],low[MAXN],instack[MAXN],dfn[MAXN],p,numtp,sum[MAXN];bool used[MAXN];stack mystack;void trajin(int h){ int i,k; low[h]=dfn[h]=++p; used[h]=instack[h]=true; mystack.push(h); k=link[h]; while (k) { if (!used[line[k].y]) { trajin(line[k].y); low[h]=min(low[h],low[line[k].y]); }else if (instack[line[k].y]) { low[h]=min(low[h],dfn[line[k].y]); //这里用low[line[k].y]来更新结果同样正确..但似乎会影响其他的找桥和割的运算 } k=line[k].next; } k=h; if (low[k]==dfn[k]) { numtp++; do { k=mystack.top(); mystack.pop(); instack[k]=true; tp[k]=numtp; }while (low[k]!=dfn[k]); } return;}void dfs(int h){ int k; used[h]=true; sum[h]++; k=link[h]; while (k) { if (!used[line2[k].y]) dfs(line2[k].y); k=line2[k].next; } return;}int getanswer(){ int i,ans,cow,k,p; p=0; numtp=0; while (!mystack.empty()) mystack.pop(); memset(used,false,sizeof(used)); for (i=1;i<=n;i++) if (!used[i]) { memset(instack,false,sizeof(instack)); trajin(i); } k=0; memset(link,0,sizeof(link)); for (i=1;i<=m;i++) if (tp[line[i].x]!=tp[line[i].y]) { k++; line2[k].x=tp[line[i].x]; line2[k].y=tp[line[i].y]; line2[k].next=link[line2[k].x]; link[line2[k].x]=k; } for (i=1;i<=n;i++) if (!tp[i]) return 0; p=n; n=numtp; memset(sum,0,sizeof(sum)); for (i=1;i<=n;i++) { memset(used,false,sizeof(used)); dfs(i); } for (i=1;i<=n;i++) if (sum[i]==n) cow=i; ans=0; for (i=1;i<=p;i++) if (tp[i]==cow) ans++; return ans;}int main(){ while (~scanf("%d%d",&n,&m)) { memset(line,0,sizeof(line)); memset(link,0,sizeof(link)); memset(tp,0,sizeof(tp)); int i; for (i=1;i<=m;i++) { scanf("%d%d",&line[i].x,&line[i].y); line[i].next=link[line[i].x]; link[line[i].x]=i; } printf("%d\n",getanswer()); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。