/* 歐拉路徑?之?poj?2513?Colored?Sticks歐拉路徑：?若圖G中存在這樣一條路徑，使得它恰通過G中每條邊一次,則稱該路徑為歐拉路徑。無向圖存在歐拉路徑?充要條件：1）?圖是連通的；2）?所有節點的度為偶數，或者有且只有兩個度為奇數的節點。題目要求：align?the?sticks?in?a?straight?line?such?that?the?colors?of?the?endpoints?that?touch?are?of?the?same?color.模型轉換：木棒看作邊，木棒兩端看作節點（相同的顏色即為同一個節點），這樣便可構成無向圖G。align?the?sticks?in?a?straight?line?即：在無向圖G中，通過每條邊一次。即：判定無向圖G是否存在歐拉路徑實現：字典樹?+?并查集*/
1 #include <crtdbg.h> 2 #include <iostream> 3 #include <fstream> 4 #include <sstream> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <cstddef> 8 #include <iterator> 9 #include <algorithm> 10 #include <string> 11 #include <locale> 12 #include <cmath> 13 #include <vector> 14 #include <cstring> 15 #include <map> 16 #include <utility> 17 #include <queue> 18 #include <stack> 19 #include <set> 20 #include <functional> 21 using namespace std; 22 typedef pair<int, int> PII; 23 typedef long long int64; 24 const int INF = 0x3f3f3f3f; 25 const int modPrime = 3046721; 26 const double eps = 1e-9; 27 const int MaxN = 500010; 28 const int MaxM = 10010; 29 30 31 int degree[MaxN]; 32 int ftr[MaxN]; 33 int rnk[MaxN]; 34 35 //Union-Find Sets 36 void ufsIni() 37 { 38 for (int i = 0; i < MaxN; ++i) 39 { 40 ftr[i] = i; 41 rnk[i] = 0; 42 } 43 } 44 int ufsFind(int x) 45 { 46 if (x == ftr[x]) return x; 47 return ftr[x] = ufsFind(ftr[x]); 48 } 49 void ufsUnite(int x, int y) 50 { 51 x = ufsFind(x); 52 y = ufsFind(y); 53 if (x == y) return; 54 55 if (rnk[x] > rnk[y]) 56 { 57 ftr[y] = x; 58 } 59 else 60 { 61 ftr[x] = y; 62 if (rnk[x] == rnk[y]) 63 { 64 ++rnk[y]; 65 } 66 } 67 } 68 69 // Tree 70 struct Tree 71 { 72 Tree *next[26]; 73 bool flag; 74 int num; 75 Tree() 76 { 77 flag = false; 78 memset(next, NULL, sizeof(next)); 79 } 80 }; 81 82 Tree *Root = new Tree; 83 84 int insertNode(string str, int num) 85 { 86 Tree *p = Root; 87 for (int i = 0; i < str.size(); ++i) 88 { 89 int pos = str[i] - 'a'; 90 if (!(p->next[pos])) 91 { 92 p->next[pos] = new Tree; 93 } 94 p = p->next[pos]; 95 } 96 if (!(p->flag)) 97 { 98 p->flag = true; 99 p->num = num; 100 } 101 return p->num; 102 } 103 104 void destroyTree(Tree *root) 105 { 106 for (int i = 0; i < 26; ++i) 107 { 108 if (root->next[i]) 109 { 110 destroyTree(root->next[i]); 111 } 112 } 113 delete[] root; 114 } 115 116 117 int main() 118 { 119 #ifdef HOME 120 freopen("in", "r", stdin); 121 //freopen("out", "w", stdout); 122 #endif 123 124 char str1[11], str2[11]; 125 int num = 0; 126 fill(degree, degree + MaxN, 0); 127 ufsIni(); 128 while (~scanf("%s %s", str1, str2)) 129 { 130 int numTmp1 = insertNode(str1, num); 131 if (numTmp1 == num) 132 { 133 ++num; 134 } 135 int numTmp2 = insertNode(str2, num); 136 if (numTmp2 == num) 137 { 138 ++num; 139 } 140 141 ++degree[numTmp1]; 142 ++degree[numTmp2]; 143 ufsUnite(numTmp1, numTmp2); 144 } 145 destroyTree(Root); 146 for (int i = 1; i < num; ++i) 147 { 148 if (ftr[i] != ftr[0]) 149 { 150 printf("Impossible\n"); 151 return 0; 152 } 153 } 154 int oddCnt = 0; 155 for (int i = 0; i < num; ++i) 156 { 157 if (degree[i] & 1) 158 { 159 ++oddCnt; 160 if (oddCnt >= 3) 161 { 162 break; 163 } 164 } 165 } 166 if (oddCnt == 0 || oddCnt == 2) 167 { 168 printf("Possible\n"); 169 } 170 else 171 { 172 printf("Impossible\n"); 173 } 174 175 176 #ifdef HOME 177 cerr << "Time elapsed: " << clock() / CLOCKS_PER_SEC << " ms" << endl; 178 _CrtDumpMemoryLeaks(); 179 #endif 180 return 0; 181 }

?

?

轉載于:https://www.cnblogs.com/shijianming/p/5099437.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的欧拉路径 之 poj 2513 Colored Sticks的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。