Detail of message

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

Tarjan算法是没有问题的

Posted by 1593767536 at 2017-09-20 14:57:36 on Problem 3207
In Reply To:Re:总觉得Tarjan算法求有向图的强连通分量不大好~好像会漏掉些特殊情况似的，比如、、、 Posted by:1593767536 at 2017-09-20 14:52:33

> if(low[p]==dfn[p]){
> 	int y;
> 	cnt++;
> 	do{
> 	    y=sta[--top];
> 	    vis[y]=2;
> 	    bel[y]=cnt;
> 	}while(y!=p);
>     }
> vis[y]=2一定要写在这里面，也可以是vis[y]=0，就是表示y不在栈中了，如果把这句话写在了外面就会导致求出来的连通分量不是强连通分量，因为不是最大的连通分量

Followed by:

Post your reply here:

Home Page Go Back To top