題目：http://acm.hdu.edu.cn/showproblem.php?pid=1116

題意：給你一些英文單詞，判斷所有單詞能不能連成一串，類似成語接龍。但是如果有多個重復(fù)的單詞時，也必須滿足這樣的條件才能算YES。否則都是不可能的情況。

分析：我們以每個單詞的首尾為節(jié)點建立有向圖，然后再判斷這個圖是否是歐拉通路或者是歐拉回路就行了。當然用并查集判斷。

那么先了解概念：

歐拉通路：除首尾結(jié)點外，其余結(jié)點入度等于出度，起點出度減入度等于1，終點入度減出度等于1。

歐拉回路：所有結(jié)點的入度都等于出度。

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 26;int pre[N]; int IN[N],OT[N],p[N]; bool vis[N]; char str[1005];void Init() {memset(vis,0,sizeof(vis));memset(IN,0,sizeof(IN));memset(OT,0,sizeof(OT));for(int i=0;i<N;i++)pre[i] = i; }int Find(int x) {if(pre[x] != x)pre[x] = Find(pre[x]);return pre[x]; }void Union(int x,int y) {x = Find(x);y = Find(y);if(x == y) return;pre[x] = y; }int main() {int T,n;scanf("%d",&T);while(T--){Init();scanf("%d",&n);while(n--){scanf("%s",str);int len = strlen(str);int x = str[0] - 'a';int y = str[len-1] - 'a';Union(x,y);OT[x]++;IN[y]++;vis[x] = vis[y] = 1;}int cnt = 0;for(int i=0;i<N;i++){pre[i] = Find(i);if(vis[i] && pre[i]==i)cnt++;}if(cnt > 1){puts("The door cannot be opened.");continue;}int k = 0;for(int i=0;i<N;i++){if(vis[i] && IN[i] != OT[i])p[k++] = i;}if(k == 0){puts("Ordering is possible.");continue;}if(k == 2 && ((OT[p[0]] - IN[p[0]] == 1 && IN[p[1]] - OT[p[1]] == 1) || (OT[p[1]] - IN[p[1]] == 1 && IN[p[0]] - OT[p[0]] == 1))){puts("Ordering is possible.");continue;}puts("The door cannot be opened.");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的并查集求欧拉回路/通路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。