思路：利用它的几条性质
#include<set> #include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pb push_back #define mp make_pair #define Maxn 20010 #define Maxm 2000010 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 100000 #define lowbit(x) (x&(-x)) #define clr(x,y) memset(x,y,sizeof(x)) #define Mod 1000000007 using namespace std; int dfn[Maxn],low[Maxn],id[Maxn],vi[Maxn],head[Maxn],use[Maxn],e,num,lab; void init() { clr(dfn,0); clr(low,0); clr(id,0); clr(vi,0); clr(use,0); clr(head,-1); e=num=lab=0; } struct Edge{ int u,v,col,f,next; }edge[Maxm]; void add(int u,int v) { edge[e].u=u,edge[e].v=v,edge[e].f=edge[e].col=0,edge[e].next=head[u],head[u]=e++; } int Tarjan(int u) { int i,v; dfn[u]=low[u]=++lab; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next){ v=edge[i].v; if(use[v]) return 0; if(!dfn[v]){ if(!Tarjan(v)) return 0; if(low[v]>dfn[u]) return 0; low[u]=min(low[u],low[v]); } if(vi[v]) low[u]=min(low[u],dfn[v]); } use[u]=1; if(low[u]==dfn[u]){ if(u!=1) return 0; } return 1; } int main() { int t,n,i,j,u,v; scanf("%d",&t); while(t--){ init(); scanf("%d",&n); while(scanf("%d%d",&u,&v),u|v){ add(u,v); } //cout<<"ok"<<endl; int f=Tarjan(1); for(i=0;i<n;i++){ if(!dfn[i]){ f=0; break; } } if(f) printf("YES "); else printf("NO "); } return 0; }