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

Re:总觉得Tarjan算法求有向图的强连通分量不大好~好像会漏掉些特殊情况似的，比如、、、

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

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:

Tarjan算法是没有问题的 (227) 1593767536 2017-09-20 14:57:36

Post your reply here:

Home Page Go Back To top