洛谷题号：P2731
参考题解：作者: 约修亚_RK 更新时间: 2016-10-28 23:59
作者: 曹彦臣 更新时间: 2016-09-07 21:31
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2731
一开始用的是Fleury’s algorithm，T了1个点：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | #include<iostream> #include<string> #include<algorithm> #include<queue> #include<list> #include<cstring> using namespace std; int f, rk = 0, mnode = 0,ans; int arr[505][505]; int path[10000]; int degree[505]; bool check(int num){ for (int i = 1; i <= mnode; i++){ for (int j = 1; j <= mnode; j++){ if (arr[i][j]!=0) return false; } } ans = num; return true; } bool dfs(int node,int depth){ path[depth] = node; bool flag = false; for (int i = 1; i <= mnode; i++){ if (arr[node][i]){ flag = true; arr[node][i]--; arr[i][node]--; if (dfs(i, depth + 1))return true; arr[node][i]++; arr[i][node]++; } } if (!flag&&check(depth))return true; path[depth] = 0; return false; } int main(){ ios::sync_with_stdio(false); cin >> f; for (int i = 1; i <= f; i++){ int u, v; cin >> u >> v; arr[u][v]++; arr[v][u]++; degree[u]++; degree[v]++; mnode = max(mnode, u); mnode = max(mnode, v); } bool odd = false; for (int i = 1; i <= mnode; i++){ if (degree[i] % 2 == 1){ odd = true; if (dfs(i, 1))break; } } if (!odd)dfs(1, 1); for (int i = 1; i <= ans; i++){ cout << path[i] << endl; } } |
后来改用Hierholzer’s algorithm，A了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | int f, rk = 0, mnode = 0,ans; int arr[505][505]; int path[10000]; int degree[505]; bool check(int num){ for (int i = 1; i <= mnode; i++){ for (int j = 1; j <= mnode; j++){ if (arr[i][j]!=0) return false; } } ans = num; return true; } void Euler(int node){ //新版本 for (int i = 1; i <= mnode; i++){ while (arr[node][i] > 0){ arr[node][i]--; arr[i][node]--; Euler(i); } } path[++ans] = node; } int main(){ ios::sync_with_stdio(false); cin >> f; for (int i = 1; i <= f; i++){ int u, v; cin >> u >> v; arr[u][v]++; arr[v][u]++; degree[u]++; degree[v]++; mnode = max(mnode, u); mnode = max(mnode, v); } bool odd = false; for (int i = 1; i <= mnode; i++){ if (degree[i] % 2 == 1){ odd = true; Euler(i); break; } } if (!odd)Euler(1); for (int i = ans; i >=1; i--){ cout << path[i] << endl; } } |