本文主要是介绍HDU-1116 Play on Words 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*
http://acm.hdu.edu.cn/showproblem.php?pid=1116
题意：
有n个字符串，问能不能将n个字符串连接起来，使得每一个字符串的首字母等于前一个字符串的尾字母，每个字符串必须连进去一次。
题解：
欧拉回路，把每个字符串看成一个一条边，一条从头到尾的有向边，首尾的两个字符看成图中的两个点，建立一个邻接矩阵。
然后求每个点的入度和出度，如果有一点入度为0，出度为1，一点入度为1，出度为0，剩余的点入度等于出度，则符合条件（或者是所有的点都是入度等于出度）。
在判断的时候可以计算每个点的入度-出度，看最后的结果中，是否出现一次1，一次-1，其余的都是0（或者是所有的结果都是0）。
*/
#include "stdio.h"
#include "string.h"
const int maxn = 30;
int n;
int p[maxn],rank[maxn],in[maxn],out[maxn];
bool vis[maxn];
char str[2005];int find( int x ) //找到最久远的祖先时“顺便”把它的子孙直接连接到它上面。
{if( p[x]==x )return x;else{p[x] = find(p[x]); //路径压缩return p[x];}
}
void merge(int a,int b) //Rank合并 合并时将元素所在深度低的集合合并到元素所在深度深的集合。
{int x = find(a);int y = find(b);if( rank[x]>rank[y] )p[y] = x;else{p[x] = y;if( rank[x]==rank[y] )rank[y]++; //重要的是祖先的rank，所以只用修改祖先的rank就可以了，子节点的rank不用管}
}void init()
{for( int i=0;i<26;i++ )p[i] = i;memset(in,0,sizeof(in));memset(out,0,sizeof(out));memset(vis,0,sizeof(vis));memset(rank,0,sizeof(rank));
}
int main()
{int t,i,x,y,len;scanf("%d",&t);while( t-- ){scanf("%d",&n);getchar();init(); //初始化for( i=1;i<=n;i++ ){gets( str );len = strlen( str );x = str[0]-'a';y = str[len-1]-'a';in[x]++; //入度out[y]++; //出度vis[x] = vis[y] = 1;merge( x,y );}int res = 0;for( i=0;i<26;i++ ){if( vis[i] && p[i]==i )res++;}if( res>1 ){puts("The door cannot be opened.");continue;}int n0=0,n1=0,n2=0;for( i=0;i<26;i++ ){int k = in[i]-out[i];if( k == 0 )n0++;else if( k == 1 )n1++;else if( k == -1 )n2++;}if((n0==24 && n1==1 && n2==1) || (n0==26 && n1==0 && n2==0) )puts("Ordering is possible.");elseputs("The door cannot be opened.");}return 0;
}这篇关于HDU-1116 Play on Words 并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
