uva10129 PlayOnWords(并查集，欧拉回路)

判断无向图是否存在欧拉回路，就是看度数为奇数的点有多少个，如果有两个，那么以那分别两个点为起点和终点，可以构造出一条欧拉回路，如果没有，就任意来，否则，欧拉回路不存在。

首先用并查集判断连通，然后统计度数。

#include<cstdio>

#include<cstring>

#include<vector>

//#include<algorithm>

//#define local

using namespace std;

const int maxl = ;

const int maxn = 1e3 + ;

int p[maxl];

bool used[maxl];//出现过的字符

char s[maxn];

int Find(int x) {return p[x] == x ? x : p[x] = Find(p[x]); }

char last(char *p)

{

   while(*(++p));

   return *(p-);

}

int deg[maxl];//出度 - 入度

#define ID(c) (c-'a')

int main()

{

#ifdef local

    freopen("in10129.txt","r",stdin);

#endif // local

   int T,N;

   scanf("%d",&T);

   while(T--) {

      memset(used,false,sizeof(used));

      memset(deg,,sizeof(deg));

      int cc = ;

      for(int i = ; i < maxl; i ++) { p[i] = i; }

      scanf("%d", &N);

      while(N--){

         scanf("%s",s);

         int u = ID(*s), v = ID(last(s));

         deg[u]++; deg[v]--;

         used[u] = used[v] = true;

         int s1 = Find(u), s2 = Find(v);

         if(s1 != s2) {

            p[s1] = s2; cc--;

         }

      }

      bool ok = false;

      for(int i = ; i < maxl; i ++) {

         if(!used[i]) cc--;

      }

      int odd[maxl] = {},top = ;

      if(cc == ){

         for(int i = ; i < maxl; i ++) if(deg[i]) {

            odd[top++] = deg[i];

         }

         if(top ==  && (odd[] ==  || odd[] == ) ) ok = true;//入度sum = 出度sum

         else if(top == ) ok = true;

      }

      if(ok) printf("Ordering is possible.\n");

      else printf("The door cannot be opened.\n");

   }

   return ;

}