dfs找环

对于dfs找环，实际上就是和图上的dfs树是一个套路，

对于一个在有向图的dfs树上的返祖边，凭借这条边必定会构成一个环，

然后我们把运行时的栈中从返祖的祖先那个点之上所有点按顺序都取出来就是我们所需要的环了。

 

void dfs(int u)
{
	if (o) return ;
	vis[u]=1;s.push(u);//vis==0表示还没有访问过,vis==1表示访问过正在栈中，vis==2表示访问过，已经出栈了
	for (int i=1;i<=n;i++) if (a[u][i]=='1') 
	{
		if (vis[i]==2) continue;
		if (vis[i]==0) {dfs(i);return ;}
		do
		{
			circal[++tot]=s.top();
			if (s.top()==i)  break;
			s.pop();
		}while (true);
		o=true;return ;
	}
	
	vis[u]=2;s.pop();
}

for (int i=1;i<=n;i++) dfs(i);//保证每一个都被访问了，在图上dfs中必须要考虑这个情况（包括有向（边的方向都一个样）无向（不连通））