PKU 2513 Colored Sticks
http://poj.org/problem?id=2513
両端に色をもつ棒の情報が渡される。
この棒の色が同じ端っこ同士をつなげて、直線が作れるかどうかを判定しろというような問題。
一筆書きできるかどうかを判定すればいいなと考えて、最初map
int un[500000]; int find(int x){ if(x==un[x])return x; return un[x]=find(un[x]); } void unit(int a,int b){ un[find(a)]=un[find(b)]=find(a); } typedef struct _node{ char key[20]; int val; _node* next; }node; const int hashMod=30000000; node* hash[hashMod]; int number; node ent[500000]; int getnum(char in[]){ int ha=0; for(char*p=in;*p;++p)ha=(ha*67+*p)%hashMod; for(node*p=hash[ha];p;p=p->next){ if(strcmp(in,p->key)==0){ return p->val; } } node*p=hash[ha]; hash[ha]=ent+number; hash[ha]->next=p; strcpy(hash[ha]->key,in); hash[ha]->val=number++; return number-1; } char in1[100],in2[100]; int deg[500000]; main(){ rep(i,500000)un[i]=i; int od=0; while(~scanf(" %s %s ",in1,in2)){ int t1=getnum(in1); int t2=getnum(in2); ++deg[t1]; ++deg[t2]; unit(t1,t2); } bool ok=true; rep(i,number){ if(deg[i]%2)++od; ok&=find(0)==find(i); } if(od<=2 && ok)printf("Possible\n"); else printf("Impossible\n"); }