題目鏈接：點擊查看

題目大意：給出n個木棍，問若兩兩相連，最終能否構成一根長直木棍，相連的規則是兩個木棍的相接端點的顏色需要保持相同

題目分析：關于這個題目，我們可以將每個木棍視為一條邊，每個木棍的兩個端點視為兩個頂點，問能否相連，我們可以聯想到歐拉回路，也就是說必須滿足下面的兩個條件：

所有的頂點能夠構成回路

所有度數為奇數的頂點只能有零個或兩個

如此一來題目就簡單多了，但還是存在許多細節需要處理，首先，判斷能否構成回路，我們可以直接用并查集，但問題就在于每個頂點題目給出的是字符串，再加上這是poj上的題，不能用哈希map映射，用普通map映射的話又要付出logn的時間代價，積少成多就會讓這個題目超時，所以我們需要換個方法映射，我是想到了用哈希，但哈希出來的答案并不是連續的，不太好用并查集，后來去網上看了題解才知道，原來字典樹還可以充當哈希，給每個單詞都規定一個編號，并且最重要的是這個編號是連續的，這樣一來就解決了映射的問題，每次查詢編號的時間復雜度只有O(10)（因為這個題目中的每個字符串最大只有10個字符的長度），當我們映射成數字之后就不用再使用那些字符串了，所以在讀入的時候也不需要儲存，在線處理即可，等到輸入結束后，先判斷一下度數情況，若度數情況都不滿足，直接輸出impossible就行了，若度數情況滿足了，我們就再用并查集查詢一下所有節點的父親是否都是同一個節點，因為在查詢的時候用了路徑壓縮，所以每次并查集查詢的時間復雜度可以達到O(1)，這樣一來時間復雜度就可以下降到O(n)了，就可以完美解決這個題目了

這個題目我感覺很好，用到了很多算法知識的結合，單個算法拿出來可能并不難，但混合到了一起就非常考驗綜合能力了

上代碼吧，實現起來并不是很復雜：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e5+100;int k=1;int cnt=0;int trie[N*10][26];int node[N*10];int f[N];int du[N];int insert(char s[]) {int len=strlen(s);int pos=0;for(int i=0;i<len;i++){int to=s[i]-'a';if(!trie[pos][to])trie[pos][to]=k++;pos=trie[pos][to];}if(node[pos])return node[pos];elsereturn node[pos]=++cnt; }int find(int x) {return x==f[x]?x:f[x]=find(f[x]); }bool check() {int sum=0;for(int i=1;i<=cnt;i++)if(du[i]&1)sum++;if(sum==1||sum>=3)return false;int target=find(1);for(int i=2;i<=cnt;i++)if(find(i)!=target)return false;return true; }int main() { // freopen("input.txt","r",stdin);for(int i=0;i<N;i++)f[i]=i;char s1[15],s2[15];while(scanf("%s%s",s1,s2)!=EOF){int a=insert(s1);int b=insert(s2);du[a]++;du[b]++;int aa=find(a);int bb=find(b);if(aa!=bb)f[aa]=bb;}if(check())printf("Possible\n");elseprintf("Impossible\n");return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的POJ - 2513 Colored Sticks(字典树+并查集+欧拉回路)的全部內容，希望文章能夠幫你解決所遇到的問題。

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