POJ2513 Colored Sticks

这道题需要判断图的连通性和欧拉回路，我的程序用了并查集判断图的连通性，用Trie树（用Hash效果也不错）统计单词出现次数，即统计的顶点的度数以此判断该图是否存在欧拉回路。

#include<iostream>

using namespace std;

#define N 500010

struct Node

{

   int id;

   Node *p[26];

   Node()

   {

      int i;

      id=-1;

      for (i=0;i<26;i++)

        p[i]=NULL;

   }

}root;

int d[N],parent[N],rank[N],cnt;

int GetNum(char *s)

{

   int i;

   Node *r=&root;

   for (i=0;s[i];i++)

   {

      if (r->p[s[i]-'a']==NULL)

        r->p[s[i]-'a']=new Node();

      r=r->p[s[i]-'a'];

   }

   if (r->id==-1)

      r->id=cnt++;

   return r->id;

}

int FindSet(int i)

{

   if (parent[i]!=i)

      parent[i]=FindSet(parent[i]);

   return parent[i];

}

int UnionSet(int i,int j)

{

   i=FindSet(i);

   j=FindSet(j);

   if (i!=j)

      if (rank[i]>rank[j])

        parent[j]=i;

      else

      {

        parent[i]=j;

        if (rank[i]==rank[j])

           ++rank[j];

      }

   return i!=j;

}

int main()

{

   int i,j,k;

   char s1[12],s2[12];

   for (i=0;i<N;i++)

      parent[i]=i;

   cnt=0;

   memset(rank,0,sizeof(rank));

   memset(d,0,sizeof(d));

   while (scanf("%s%s",s1,s2)!=EOF)

   {

      j=GetNum(s1);

      k=GetNum(s2);

      d[j]++;

      d[k]++;

      UnionSet(j,k);

   }

   for (k=i=0;i<cnt;i++)

      if (d[i]%2)

        k++;

   j=FindSet(0);

   for (i=1;i<cnt;i++)

      if (FindSet(i)!=j)

      {

        printf("Impossible\n");

        return 0;

      }

   if (k<3)

      printf("Possible\n");

   else

      printf("Impossible\n");

   return 0;

}