就是判断一个有向图是否有环，注意图可能不连通。
用dfs搜一下就行了。
1 #include<cstdio> 2 #include<cstring> 3 int n,m,t,h[100001],v[100001]; 4 struct node{ 5 int next,to; 6 }e[500001]; 7 int dfs(int i){ 8 v[i]=-1; 9 for(int j=h[i];j;j=e[j].next){ 10 int t=e[j].to; 11 if(v[t]<0) return 0; //如果和它邻接的边也在搜索栈中，说明是环 12 else if(!v[t]&&!dfs(t)) return 0; //即使没在搜索栈，但是它的下一条边不符合 13 } 14 v[i]=1; return 1; //包含当前结点的路径搜完了且无环路 15 } 16 int check(){ 17 for(int i=1;i<=n;i++) 18 if(!v[i]) 19 if(!dfs(i)) return 0; //0表示有环，1表示无环 20 return 1; 21 } 22 int main() 23 { 24 scanf("%d",&t); 25 while(t--){ 26 memset(v,0,sizeof v); 27 memset(h,0,sizeof h); //注意到h[]也要初始化 28 scanf("%d%d",&n,&m); 29 for(int i=1;i<=m;i++){ 30 int x,y; 31 scanf("%d%d",&x,&y); 32 e[i].next=h[x]; 33 e[i].to=y; 34 h[x]=i; 35 } 36 if(check()) printf("No "); 37 else printf("Yes "); 38 } 39 }