Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator