UVA10129———欧拉道路

题目

输入n(n≤100000)个单词，是否可以把所有这些单词排成一个序列，使得每个单词的第一个字母和上一个单词的最后一个字母相同（例如 acm,malform,mouse）。每个单词最多包含1000个小写字母。输入中可以有重复单词。

解题思路

把字母看作结点，单词看作有向边，则问题有解等价于图中存在欧拉道路。有向图中存在欧拉道路的条件有两个：一是底图（忽略边的方向后得到的无向图）连通，二是度数满足不存在奇点或奇点数为2。度数判读只要在输入时记录每个顶点的入度出度，而连通性判断有两种：DFS和并查集。

代码实现

dfs判断连通性+特判入出度

 #include<stdio.h>

 #include<cstring>

 using namespace std;

 const int maxn =  + ;

 int G[maxn][maxn],in[maxn],out[maxn];

 int vis[maxn];        //点是否访问，不是边

 int n;

 char word[ + ];

 void dfs(int u)

 {

     vis[u] = ;

     for (int v = ; v < maxn; v++)  if (G[u][v])

     {

         G[u][v] = G[v][u] = ;

         //G[u][v]--; G[v][u]--;

         dfs(v);

     }

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while (T--)

     {

         memset(G, , sizeof(G));

         memset(in, , sizeof(in));

         memset(out, , sizeof(out));

         memset(vis, , sizeof(vis));

         scanf("%d", &n);

         int start;            //起点

         while (n--)

         {

             scanf("%s", word);

             int len = strlen(word);

             int u = word[] - 'a', v = word[len - ] - 'a';

             start = u;

             vis[u] = vis[v] = -;    //出现过的标为-1

             G[u][v] = G[v][u] = ;    //连通性按无向图处理

             //G[u][v]++; G[v][u]++;

             out[u]++;        //度数按有向图处理

             in[v]++;

         }

         bool flag = true;    //满足要求为true

         int s_odd = ,t_odd = ;    //起始奇点、结束奇点

         for (int i = ; i < maxn; i++)

         {

             if (in[i] == out[i])  continue;

             if (out[i] == in[i] +  && !s_odd) { start = i; s_odd = ; }

             else if (in[i] == out[i] +  && !t_odd)  t_odd = ;

             else { flag = false; break; }

         }

         if (flag)

         {

             dfs(start);    //也可以不从奇点出发，这个只是判断连通性

             for (int i = ; i < maxn; i++)

                 if (vis[i] == -) { flag = false; break; }

         }

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

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

     }

     return ;

 }

并查集判断连通性+特判入出度

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<string>

 #include<cmath>

 using namespace std;

 const int maxn =  + ;

 int in[maxn], out[maxn], flag[maxn], p[maxn], fa[maxn];

 int n;

 void init()

 {

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

         fa[i] = i;

     memset(in, , sizeof(in));

     memset(out, , sizeof(out));

     memset(flag, , sizeof(flag));

     memset(p, , sizeof(p));

 }

 int find(int x)

 {

     if (fa[x] != x)    return fa[x] = find(fa[x]);

     return fa[x];

 }

 void unite(int x, int y)

 {

     int rx = find(x);

     int ry = find(y);

     fa[rx] = ry;

 }

 int main()

 {

     int T;

     int a, b;

     string str;

     scanf("%d", &T);

     while (T--)

 {

         init();

         scanf("%d", &n);

         for (int i = ; i < n; i++)

         {

             cin >> str;

             a = str[] - 'a';

             b = str[str.size() - ] - 'a';

             unite(a, b);

             in[a]++;

             out[b]++;

             flag[a] = flag[b] = ;

         }

         int cnt = ;    //记录连通分量

         int root;

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

         {

             if (flag[i])

             {

                 root = find(i);

                 break;

             }

         }

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

         {

             if (flag[i])

                 if (root != find(i)) cnt = ;

         }

         if (cnt) {

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

             continue;

         }

         int k = ; //p[i]记录度数不等的

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

         {

             if (flag[i] && in[i] != out[i])  p[k++] = i;

         }

         if (k == )

         {

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

             continue;

         }

         if (k ==  && (in[p[]] - out[p[]] ==  && in[p[]] - out[p[]] == -) || (in[p[]] - out[p[]] == - && in[p[]] - out[p[]] == ))

         {

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

         continue;

         }

         else

         {

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

         }

     }

     return ;

 }

参考链接：https://blog.csdn.net/qq_29169749/article/details/51111377