义乌网站建设现状潮州seo建站

判环用什么？

用tarjan？拓扑排序？

其实都不用，用dfs+栈即可解决问题。（前提是不考虑时间复杂度）

我们只需要一个bool数组in_stack，每dfs到一个点，把点压入栈中，并把in_stack设为true，如果访问到一个节点已经在栈中，就依次取出栈中元素直到取到访问到的那个节点为止。

Code

int n,g[maxn][maxn],st[maxn],top;
bool oncyc[maxn],inst[maxn];
void getcyc(int u){st[++top]=u;inst[u]=1;int count=0;for(int v=1;v<=n;v++){if(!g[u][v])continue;count+=g[u][v];if(!inst[v]){getcyc(v);}else{int t;for(t=top;st[t]!=v;t--);for(int i=t;i<=top;i++){printf("%d ~ ",st[i]);}puts("");}top--;inst[u]=0;
}