题意:
给了一堆木棍..木棍的的两头都有颜色..木棍可以通过颜色相同的连在一起..问能否将所有木棍连成一条直线....
题解:
乍一看也是一个求哈密顿通路的问题..同样要进行问题转化..把颜色看成点..把每个木棍看成边..那么问题就变成了求是否存在欧拉通路...
无向图的欧拉通路:
1、其存在欧拉回路也必定就存在欧拉通路..因为通路的范围包括了回路
2、不考虑欧拉回路的情况..那么就需要exactly 两个点的度为奇数..其余的都为偶数...并且是连通图
本题用map搞会超时..要写一个字点树...so easy啦~
Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<queue> #include<stack> #include<set> #include<time.h> #include<map> #include<algorithm> #define ll long long #define eps 1e-5 #define oo 1000000007 #define pi acos(-1.0) #define MAXN 500005 #define MAXM 500005 using namespace std; struct node { int son[26],id; }T[100005]; int father[MAXN],P[MAXN],N; char ss[15]; int trie(char *s,int &num) { int h=0,len=strlen(s),i; for (i=0;i<len;i++) { if (!T[h].son[s[i]-'a']) T[h].son[s[i]-'a']=++N; h=T[h].son[s[i]-'a']; } if (T[h].id) return T[h].id; return T[h].id=++num; } int getfather(int x) { if (father[x]==x) return x; return father[x]=getfather(father[x]); } bool judge(int n,int m) { int i,t=0; if (n==1) return true; for (i=1;i<=n;i++) if (getfather(i)!=m) return false; for (i=1;i<=n;i++) if (P[i]%2) t++; if (!t || t==2) return true; return false; } int main() { int x,y,m,num=0; for (x=1;x<=500000;x++) father[x]=x; memset(P,0,sizeof(P)); memset(T,0,sizeof(T)),N=0; while (~scanf("%s",ss)) { x=trie(ss,num); scanf("%s",ss); y=trie(ss,num); father[getfather(x)]=getfather(y); P[x]++,P[y]++; m=getfather(x); } if (judge(num,m)) printf("Possible\n"); else printf("Impossible\n"); return 0; }