题意：判断题目中给出的图是否符合两个条件。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[];
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,,sizeof(dfn));
memset(low,,sizeof(low));
memset(fa,-,sizeof(fa));
memset(node,,sizeof(node));
memset(id,,sizeof(id));
all = ,sum = ;
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 != -;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] >= )
{
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,-,sizeof(head));
tot = ;
while(~scanf("%d%d",&x,&y))
{
if(!x && !y) break;
add_edge(x,y);
}
init();
for(int i = ;i < n;i++)
{
if(!dfn[i])
tarjan(i);
}
if(sum >= ) flag1 = false;
///cout<<"sum = "<<sum<<endl;
if(flag1 && flag2) printf("YES\n");
else printf("NO\n");
}
return ;
}