1 /* 2 这道题如果按照度为0的节点来判断的时候,将度为0的节点和其相连的节点(度数并减去1) 3 从图中去掉,如果度为0的节点的个数为0个但是图中的节点没有都去掉的 时候那么说明 4 出现了回路!用这种方法必须将重边去除掉! 5 6 所以推荐用dfs方式进行判断!这种方式还是比较直观的! 7 */ 8 #include<iostream> 9 #include<cstring> 10 #include<cstdio> 11 #include<algorithm> 12 using namespace std; 13 14 int used[30]; 15 int deg[30]; 16 int map[30][30]; 17 int sum; 18 bool topoSort(){ 19 for(int i=1; i<=sum; ++i){ 20 int cnt=0, p; 21 for(int j=0; j<26; ++j) 22 if(used[j] && deg[j]==0) { 23 ++cnt; 24 p=j; 25 } 26 if(cnt==0) return false; 27 for(int j=0; j<26; ++j) 28 if(map[p][j]){ 29 map[p][j]=0; 30 --deg[j]; 31 } 32 deg[p]=-1; 33 } 34 return true; 35 } 36 37 int main(){ 38 int m; 39 char ch[5]; 40 while(cin>>m){ 41 memset(used, 0, sizeof(used)); 42 memset(deg, 0, sizeof(deg)); 43 memset(map, 0, sizeof(map)); 44 while(m--){ 45 cin>>ch; 46 used[ch[0]-'A'] =1; 47 used[ch[2]-'A'] =1; 48 if(ch[1]=='>'){ 49 if (map[ch[2]-'A'][ch[0]-'A'] != 1) {//去掉多重边 50 ++deg[ch[0]-'A']; 51 map[ch[2]-'A'][ch[0]-'A']=1; 52 } 53 } 54 else{ 55 if (map[ch[0]-'A'][ch[2]-'A'] != 1) { 56 ++deg[ch[2]-'A']; 57 map[ch[0]-'A'][ch[2]-'A']=1; 58 } 59 } 60 } 61 sum=0; 62 for(int i=0; i<26; ++i) 63 if(used[i]) ++sum; 64 if(topoSort()) 65 cout<<"YES"<<endl; 66 else cout<<"NO"<<endl; 67 } 68 return 0; 69 } 70 71 */ 72 73 #include<iostream> 74 #include<cstring> 75 #include<cstdio> 76 #include<algorithm> 77 using namespace std; 78 int map[30][30]; 79 int vis[30]; 80 81 bool dfs(int cur){ 82 vis[cur]=-1; 83 for(int i=0; i<26; ++i) 84 if(map[cur][i]){ 85 if(vis[i]==-1) return false; 86 if(!vis[i] && !dfs(i)) return false; 87 } 88 vis[cur]=1; 89 return true; 90 } 91 92 int main(){ 93 int m; 94 char ch[5]; 95 while(cin>>m){ 96 memset(vis, 0, sizeof(vis)); 97 memset(map, 0, sizeof(map)); 98 while(m--){ 99 cin>>ch; 100 if(ch[1]=='>') 101 map[ch[2]-'A'][ch[0]-'A']=1; 102 else 103 map[ch[0]-'A'][ch[2]-'A']=1; 104 } 105 int flag=0; 106 for(int i=0; i<26; ++i) 107 if(!vis[i]) 108 if(!dfs(i)){ 109 flag=1; 110 break; 111 } 112 if(flag) cout<<"NO"<<endl; 113 else cout<<"YES"<<endl; 114 } 115 return 0; 116 }
本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3911559.html,如需转载请自行联系原作者