Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4322 Accepted Submission(s): 1926
1 #include<string> 2 #include<cstdio> 3 #include<iostream> 4 #include<vector> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<cstring> 9 #include<stdlib.h> 10 #include<string> 11 #include<cmath> 12 using namespace std; 13 #define pb push_back 14 vector<int >p[10010]; 15 int in[10010],n,m,deep[10010],num[10010]; 16 void init(){ 17 memset(in,0,sizeof(in)); 18 memset(deep,0,sizeof(deep)); 19 memset(num,0,sizeof(num)); 20 for(int i=0;i<=n;i++) p[i].clear(); 21 } 22 void tuopu(){ 23 queue<int >ak_47; 24 int cnt=0; 25 for(int i=0;i<n;i++) 26 if(in[i]==0) 27 ak_47.push(i),deep[i]=1,num[1]++; 28 while(!ak_47.empty()){ 29 int pos=ak_47.front(); 30 cnt++; 31 for(int i=0;i<p[pos].size();i++){ 32 int to=p[pos][i]; 33 if(--in[to]==0) ak_47.push(to),deep[to]=deep[pos]+1,num[deep[to] ]++; 34 } 35 ak_47.pop(); 36 } 37 if(cnt<n) cout<<"NO"<<endl; 38 else cout<<"YES"<<endl; 39 40 } 41 int main(){ 42 while(cin>>n>>m,n){ 43 init(); 44 for(int i=1;i<=m;i++){ 45 int a,b; 46 scanf("%d%d",&a,&b); 47 in[b]++; 48 p[a].pb(b); 49 } 50 tuopu(); 51 } 52 }
原文:http://www.cnblogs.com/ainixu1314/p/3896055.html