Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:总觉得Tarjan算法求有向图的强连通分量不大好~好像会漏掉些特殊情况似的,比如、、、In Reply To:总觉得Tarjan算法求有向图的强连通分量不大好~好像会漏掉些特殊情况似的,比如、、、 Posted by:Moon_1st at 2011-04-02 14:27:58 void tarjan(int x) { dfn[x]=low[x]=++num; s[++p]=x,v[x]=1; for(int i=head[x];i;i=next[i]) if(!dfn[ver[i]]) { tarjan(ver[i]); low[x]=min(low[x],low[ver[i]]); } else if(v[ver[i]]) low[x]=min(low[x],dfn[ver[i]]); if(low[x]==dfn[x]) { int y; ++t; do{y=s[p--],v[y]=0; c[y]=t;}while(y!=x); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator