Description
You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?Input
Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.Output
If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.Sample Input
blue red red violet cyan blue blue magenta magenta cyanSample Output
PossibleHint
Huge input,scanf is recommended. #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=5000010; int cnt;//hash struct Ties//Ties 进行hash { int id; Ties *next[26]; Ties() { id=-1; for(int i=0;i<26;i++) next[i]=NULL; } }; Ties *root=new Ties(); int TiesSearch(char *word) { Ties *loc=root; int i=0; while(word[i]) { int tmp=word[i]-'a'; if(loc->next[tmp]==NULL) loc->next[tmp]=new Ties(); loc=loc->next[tmp]; i++; } if(loc->id==-1) loc->id=++cnt; return loc->id; } void del(Ties* root) { if(root==NULL) return ; Ties* loc=root; for(int i=0;i<26;i++) { if(loc->next[i]!=NULL) del(loc->next[i]); } delete loc; } int fath[N];//并查集 int find(int x)//并查集判断是否连通 { return fath[x]==x?x:fath[x]=find(fath[x]); } void uion(int x,int y) { x=find(x);y=find(y); if(x==y) return ; fath[x]=y; } //判断欧拉路 int d[N];//度 int main() { for(int i=1;i<N;i++) fath[i]=i; char c[30],e[30]; while(scanf("%s%s",c,e)==2) { int x=TiesSearch(c),y=TiesSearch(e); uion(x,y); d[x]++,d[y]++; } int flag=1; //判断是否连通 int x1=find(1); for(int i=2;i<=cnt;i++) { if(find(i)!=x1) { flag=0;break; } } //判断是否是欧拉路:只有两个点度是奇数，其余点的度都是偶数 // 欧拉回路:所有点的度都是偶数 if(flag) { int tmp=0; for(int i=1;i<=cnt;i++) { if(d[i]&1) tmp++; } if(tmp>2) flag=0; } if(flag) printf("Possible/n"); else printf("Impossible/n"); del(root); return 0; }