题意：判断题目中给出的图是否符合两个条件。1 这图只有一个强连通分量 2 一条边只能出现在一个环里。
思路：条件1的满足只需要tarjan算法正常求强连通分量即可，关键是第二个条件，我们把对边的判断转化为对点的记录，在tarjan深搜的过程中，使用fa数组记录一下搜索的过程，即每个节点的父子关系，当我们发现一条回边的时候，我们从这个点使用fa向前追溯，追溯过程中建立一个数组记录每个节点的情况，只要这个点处于一个环里，就给它加1，如果这个点的值大于了一，也就意味着有这个点同时属于两个环，同意意味着有一条边同时属于两个环。
注意：在判断一个点是否同时属于两个环的时候，环的汇聚点是不可以判断的！汇聚点完全可以属于两个环，但是却没有边同时属于两个环。
在追随过程中不要修改u和v的值，否则会出现强连通分量的判断错误。
代码如下：
#include<iostream> #include<cstdio> #include<stack> #include<cstring> using namespace std; #define maxn 20020 int dfn[maxn],low[maxn],fa[maxn],node[maxn],head[maxn],id[maxn]; struct EDGE { int to,nxt; }edge[50050]; int tot,all,sum; void add_edge(int x,int y) { edge[tot].to = y; edge[tot].nxt = head[x]; head[x] = tot++; } stack<int>s; bool flag1,flag2; void init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(fa,-1,sizeof(fa)); memset(node,0,sizeof(node)); memset(id,0,sizeof(id)); all = 0,sum = 0; while(!s.empty()) s.pop(); flag1 = true,flag2 = true; } void tarjan(int u) { s.push(u); dfn[u] = low[u] = ++all; for(int i = head[u];i != -1;i = edge[i].nxt) { int v = edge[i].to; if(!dfn[v]) { fa[v] = u; tarjan(v); low[u] = min(low[u],low[v]); } else if(!id[v]) { low[u] = min(low[u],dfn[v]); int tmp = u; while(fa[tmp] != v)///此处便避开了汇聚点 { node[tmp]++; if(node[tmp] >= 2) { flag2 = false; return; } tmp = fa[tmp]; } } } if(low[u] == dfn[u]) { sum++; while(!s.empty()) { int num = s.top(); s.pop(); id[num] = sum; if(num == u) break; } } return; } int main() { int t,n,x,y; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(head,-1,sizeof(head)); tot = 0; while(~scanf("%d%d",&x,&y)) { if(!x && !y) break; add_edge(x,y); } init(); for(int i = 0;i < n;i++) { if(!dfn[i]) tarjan(i); } if(sum >= 2) flag1 = false; ///cout<<"sum = "<<sum<<endl; if(flag1 && flag2) printf("YES "); else printf("NO "); } return 0; }