| ||||||||||
| 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