首页 > 代码库 > 无向图输出所有环。。【GYN给的题目和模型都错了。。。】
无向图输出所有环。。【GYN给的题目和模型都错了。。。】
昨晚和今早帮GYN巧了一个小的算法
他的本意是把一个图的单环全部输出出来
结果建图的时候就出现问题了。。
应该是做一下修改就可以
但是我现在让他搞得目的都不知道干啥了。。
代码先放着
回去他跟我说了题意我在改
【这个要是写成了 也算是我项目上的第一个助攻了 哈哈】
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 #include <map> 6 #include <algorithm> 7 using namespace std; 8 9 const int maxn = 105; 10 int G[maxn][maxn]; 11 int s[maxn]; 12 int vis[maxn]; 13 int in[maxn]; 14 15 int n; 16 int top; 17 18 map<string, int> mp; 19 bool check1(int a[maxn], int cnt) { 20 int aa[maxn]; 21 for(int i = 0; i < cnt; i++) aa[i] = a[i]; 22 sort(aa, aa + cnt); 23 string s1; 24 for(int i = 0; i < cnt; i++) { 25 s1 += aa[i] + ‘0‘; 26 } 27 if(mp[s1]) return false; 28 else { 29 mp[s1] = 1; 30 return true; 31 } 32 } 33 34 bool check2(int a[maxn], int cnt) { 35 for(int i = 0; i < cnt; i++) { 36 for(int j = 0; j < cnt; j++) { 37 if(G[a[i]][a[j]]) { 38 if(i == 0 && j == cnt - 1) continue; 39 if(j - i >= 2) { 40 return false; 41 } 42 } 43 } 44 } 45 return true; 46 } 47 48 bool check3(int a[maxn], int cnt) { 49 } 50 51 void dfs(int x0, int x1) { 52 vis[x1] = true; 53 s[++top] = x1; 54 in[x1] = true; 55 for(int i = 1; i <= n; i++) { 56 if(i == x0 || i == x1) continue; 57 if(G[x1][i]) { 58 if(in[i]) { 59 int j; 60 for(j = top; s[j] != i; j--); 61 int che[maxn]; 62 int cnt = 0; 63 for(int k = j; k <= top; k++) { 64 che[cnt++] = s[k]; 65 } 66 if(check1(che, cnt) && check2(che, cnt)) { 67 for(int k = 0; k < cnt; k++) { 68 printf(k == 0 ? "%d" : " %d", che[k]); 69 } puts(""); 70 } 71 } else { 72 dfs(x1, i); 73 } 74 } 75 } 76 top--; 77 in[x1] = 0; 78 } 79 80 int main() { 81 int num; 82 while(EOF != scanf("%d",&n) ) { 83 memset(G, 0, sizeof(G)); 84 memset(s, 0, sizeof(s)); 85 memset(in, 0, sizeof(in)); 86 int u; 87 mp.clear(); 88 for(int i = 1; i <= n; i ++) { 89 scanf("%d",&u); 90 for(int j = 0; j < 4; j++) { 91 scanf("%d",&num); 92 if(num != 0) 93 G[u][num] = G[num][u] = 1; 94 } 95 } 96 top = 0; 97 dfs(1, 1); 98 } 99 return 0;100 }
无向图输出所有环。。【GYN给的题目和模型都错了。。。】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。