题意:给出n个单词,问这n个单词能否首尾接龙,即能否构成欧拉道路
按照紫书上的思路:用并查集来做,取每一个单词的第一个字母,和最后一个字母进行并查集的操作
但这道题目是欧拉道路(下面摘自http://blog.****.net/hcbbt/article/details/9316301)
关于欧拉道路(from Titanium大神):
判断有向图是否有欧拉路
1.判断有向图的基图(即有向图转化为无向图)连通性,用简单的DFS即可。如果图都不连通,一定不存在欧拉路
2.在条件1的基础上 对于欧拉回路,要求苛刻一点,所有点的入度都要等于出度,那么就存在欧拉回路了
对于欧拉道路,要求松一点,只有一个点,出度比入度大1,这个点一定是起点; 一个点,入度比出度大1,这个点一定是终点.其余点的出度等于入度
(注意,只能大1,而且这样的点分别只能有1个,而且存在起点就一定要存在终点,存在终点就一定要存在起点)
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL;
int degree[],pre[],in[],out[];
char s[]; int find(int root){
return root == pre[root] ? root : pre[root] = find(pre[root]); } int main(){
int t,n,i,j,flag,len,root;
cin>>t;
while(t--){
cin>>n; for(i=;i<=;i++)
pre[i]=i;
memset(in,,sizeof(in));
memset(out,,sizeof(out)); for(i=;i<=n;i++){
cin>>s;
len=strlen(s); int u=s[]-'a';int v=s[len-]-'a';
out[u]++;in[v]++; pre[find(u)]=find(v);
root=find(v);
} int ans=,inn=,outt=;
for(i=;i<=;i++){
if(in[i]||out[i]) {//如果入度或者出度 有一个存在,才继续判断
if(find(pre[i])!=root)//判断是否属于同一个联通块
ans++;
if(in[i]-out[i]==) //如果入度比出度大1的点的个数大于1,则不满足条件
inn++;
else if(out[i]-in[i]==)
outt++;
else if(abs(in[i]-out[i])>)
break;
}
} if(i<=||ans>||inn>||outt>) printf("The door cannot be opened.\n"); //i<=30表明没有正常跳出循环,不构成欧拉道路
else printf("Ordering is possible.\n");
}
return ;
}