网站建设.龙兵,房产网合肥,广州黄埔建网站,seo网站推广公司1 /*2 这道题如果按照度为0的节点来判断的时候,将度为0的节点和其相连的节点#xff08;度数并减去1#xff09; 3 从图中去掉#xff0c;如果度为0的节点的个数为0个但是图中的节点没有都去掉的 时候那么说明4 出现了回路!用这种方法必须将重边去除掉#xff01; … 1 /*2 这道题如果按照度为0的节点来判断的时候,将度为0的节点和其相连的节点度数并减去1 3 从图中去掉如果度为0的节点的个数为0个但是图中的节点没有都去掉的 时候那么说明4 出现了回路!用这种方法必须将重边去除掉 5 6 所以推荐用dfs方式进行判断这种方式还是比较直观的 7 */8 #includeiostream9 #includecstring10 #includecstdio11 #includealgorithm12 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 i1; isum; i){20 int cnt0, p;21 for(int j0; j26; j)22 if(used[j] deg[j]0) {23 cnt;24 pj;25 }26 if(cnt0) return false;27 for(int j0; j26; 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(cinm){41 memset(used, 0, sizeof(used));42 memset(deg, 0, sizeof(deg));43 memset(map, 0, sizeof(map));44 while(m--){45 cinch; 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 sum0;62 for(int i0; i26; i)63 if(used[i]) sum;64 if(topoSort())65 coutYESendl;66 else coutNOendl;67 }68 return 0;69 } 70 71 */72 73 #includeiostream74 #includecstring75 #includecstdio76 #includealgorithm77 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 i0; i26; 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(cinm){96 memset(vis, 0, sizeof(vis)); 97 memset(map, 0, sizeof(map));98 while(m--){99 cinch;
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 flag0;
106 for(int i0; i26; i)
107 if(!vis[i])
108 if(!dfs(i)){
109 flag1;
110 break;
111 }
112 if(flag) coutNOendl;
113 else coutYESendl;
114 }
115 return 0;
116 } 转载于:https://www.cnblogs.com/hujunzheng/p/3911559.html
