PKU 2513 Colored Sticks

http://poj.org/problem?id=2513
両端に色をもつ棒の情報が渡される。
この棒の色が同じ端っこ同士をつなげて、直線が作れるかどうかを判定しろというような問題。

一筆書きできるかどうかを判定すればいいなと考えて、最初mapを使ったら普通にTLEして、仕方ないからハッシュを自分で書いたらランタイムエラーして、よく考えたら棒の色は500000通りあるということに気づいて配列のサイズ直したらWAになって、しばらく悩んだ後連結性を判定してなかったのでunion-find書いたら何とか通りました。

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");
}