一開始想用map來搞，但是感覺好復雜，然后想了一下看大佬們用trie做的，感覺十分合理就敲了一發。

一開始re，數組要開到550000

只會靜態的字典樹，在每個根節點看是否出現過改顏色，如果沒有就把該點顏色記做++num

然后就是歐拉通路的一般做法，全部加到入度里，入度為奇數的個數為0或者2，然后用樹處理過的離散后的顏色進行并查集的合并，然后看是否聯通即可。

代碼如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
const double pi=acos(-1.0);
const double E=2.718281828459;
using namespace std;
const int maxn=550000;
const int N=26;
int f[maxn];
int val[maxn];
int ch[maxn][N];
int in[maxn];
int num;
int cnt,root;
int find(int x)
{return x==f[x]?x:f[x]=find(f[x]);
}
void unionn(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy)f[fx]=fy;
}
int newnode()
{for(int i=0;i<N;i++)ch[cnt][i]=0;val[++cnt]=0;return cnt-1;
}
void init()
{for(int i=0;i<=500000;i++)f[i]=i;cnt=0;num=0;root=newnode();memset(in,0,sizeof(in));
}
int insert(char *s)//插入返回顏色數
{int len=strlen(s);int u=0;for(int i=0;i<len;i++){int v=s[i]-'a';if(!ch[u][v])ch[u][v]=newnode();u=ch[u][v];}if(!val[u])val[u]=++num;return val[u];
}
char a[11],b[11];
int main()
{init();while(scanf("%s%s",a,b)!=EOF){int x=insert(a);int y=insert(b);unionn(x,y);in[x]++,in[y]++;}int con=0;int a=0;for(int i=1;i<=num;i++){if(find(i)==i)con++;if(in[i]%2==1)a++;}if(a==1||a>=3||con>1)//奇數點的個數和并查集根的個數判斷 ，oula判斷條件printf("Impossible\n");elseprintf("Possible\n");return 0;
}

?

總結

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

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