是一道歐拉路的題竟然沒看出來......
把每種顏色看成一個點，每根木棍看成一個邊，即相同顏色在圖中接好合併成了一個點，
問題轉化為了求是否存在歐拉路
如果用map會超時，所以可以用字典樹實現離散化/哈希，unordered_map需要c++11
注意判斷圖是否聯通，用并查集即可
#include<iostream> #include<cstdio> #include<cstring> #include<unordered_map> using namespace std; const int maxn=250010*2;//點數 int x,y,cnt,n;char s[15]; int deg[maxn]; int fa[maxn]; int find(int x){ while(x!=fa[x])x=fa[x]=fa[fa[x]]; return x; } bool unionn(int x,int y){ x=find(x),y=find(y); if(x==y)return 0; fa[x]=y;return 1; } //字典樹 int nod=1,root=1; struct node{ int son[26],num; }t[maxn*2]; int ask(char *s){ int k=root;char c; for(int i=0;s[i];i++){ c=s[i]-'a'; if(!t[k].son[c])t[k].son[c]=++nod;//動態開點 k=t[k].son[c]; } if(!t[k].num)t[k].num=++n; return t[k].num; } //unordered_map<string,int>m; //int ask(char *s){ // return m[s]?m[s]:m[s]=++n; //} int main(){ for(int i=1;i<=maxn;i++)fa[i]=i; while(~scanf("%s",s)){ x=ask(s); scanf("%s",s); y=ask(s); if(unionn(x,y))++cnt; ++deg[x],++deg[y]; } if(cnt<n-1){printf("Impossible");return 0;}//判聯通 int tot=0;//記錄奇點個數 for(int i=1;i<=n;i++){ if(deg[i]&1)tot++; if(tot>2){printf("Impossible");return 0;} } printf("Possible"); }