首页 > 代码库 > UVa 10129 (并查集 + 欧拉路径) Play on Words

UVa 10129 (并查集 + 欧拉路径) Play on Words

2024-07-24 06:03:56   219人阅读

题意：

有n个由小写字母的单词，要求判断是否存在某种排列是的相邻的两个单词，前一个单词末字母与后一个单词首字母相同。

分析：

将单词的两个字母看做节点，则一个单词可以看做一条有向边。那么题中所求的排列就等价于该有向图中是否存在欧拉路径。

在判断之前，首先要确定这个图是连通的，代码中用并查集来实现。

回顾一下存在欧拉路径的条件，全都是偶点或者有且仅有两个奇点。我们用deg来记录每个点的度，出度为1，入度为-1。

程序中判断存在欧拉路径的条件就是：deg全为0 或者 有两个不为0的，其中一个为1一个为-1

used记录某个字母是否出现过。

 

 1 //#define LOCAL 2 #include <vector> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 1000 + 10; 8 char word[maxn]; 9 int pa[256], deg[256], cc, used[256];10 11 int find(int a)12 { return pa[a] == a ? a : pa[a] = find(pa[a]); }13 14 int main(void)15 {16     #ifdef LOCAL17         freopen("10129in.txt", "r", stdin);18     #endif19 20     int T, n;21     scanf("%d", &T);22     while(T--)23     {24         memset(used, 0, sizeof(used));25         memset(deg, 0, sizeof(deg));26         for(int i = ‘a‘; i <= ‘z‘; ++i)27             pa[i] = i;28         cc = 26;    //Á¬Í¨¿éµÄÊýÁ¿ 29 30         scanf("%d", &n);31         for(int i = 0; i < n; ++i)32         {33             scanf("%s", word);34             char c1 = word[0];35             char c2 = word[strlen(word) - 1];36             used[c1] = used[c2] = 1;37             deg[c1]++;    deg[c2]--;38             int p1 = find(c1);39             int p2 = find(c2);40             if(p1 != p2)41             {42                 cc--;43                 pa[p1] = p2;44             }45         }46 47         vector<int> d;48         for(int i = ‘a‘; i <= ‘z‘; ++i)49         {50             if(!used[i]) --cc;51             else if(deg[i])    d.push_back(i);52         }53         bool ok = false;54         if(cc == 1 && (d.empty() || (d.size() == 2 && (deg[d[0]] == 1 || deg[d[0]] == -1)))) ok = true;55         if(ok)    puts("Ordering is possible.");56         else puts("The door cannot be opened.");57     }58 59     return 0;60 }
代码君

 

UVa 10129 (并查集 + 欧拉路径) Play on Words


联系
我们