題意：給定一系列的單詞，這些單詞要使用類似與成語接龍的方式將他們連接起來，現在問是否存在這樣一個通路。

解法：為什么這種題目剛看起來總是像那個什么哈密頓回路呢？歐拉回路主要解決對邊的遍歷問題，因此我們需要將已知條件轉移到邊上的信息即可。對于一個單詞acm，那么就連接一條從a到m的邊，那么走這條邊也就訪問了這個單詞。有向圖判定是否存在歐拉路徑的方法是：在保證圖連通的情況下，所有點的入度等于出度或者是存在兩個點，一個點入度比出度大1，另一個點出度比入度大1。

代碼如下：

#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <algorithm> #include <vector> using namespace std;int set[30]; int N, odd, in[30], out[30]; int hav[30]; vector<int>v;int find(int x) {return set[x] = x == set[x] ? x : find(set[x]); }void merge(int a, int b) {set[a] = b; }int main() {int T, ok;char str[1005];scanf("%d", &T);while (T--) { for(int i = 0; i < 26; ++i) {hav[i] = 0;set[i] = i; }v.clear();scanf("%d", &N);ok = 0;memset(in, 0, sizeof (in));memset(out, 0, sizeof (out));for (int i = 0; i < N; ++i) {scanf("%s", str);char a = str[0]-'a', b = str[strlen(str)-1]-'a';++out[a];++in[b];hav[a] = hav[b] = 1;merge(find(a), find(b));}for (int i = 0; i < 26; ++i) {if (set[i] == i && hav[i]) {++ok;}if (in[i] != out[i]) {v.push_back(i);}}if (ok != 1) {puts("The door cannot be opened.");continue;}if (v.size() > 2) {puts("The door cannot be opened."); } else if (v.size() == 2){if ((in[v[0]]-out[v[0]])*(in[v[1]]-out[v[1]]) == -1) {puts("Ordering is possible.");} else {puts("The door cannot be opened.");}} else {puts("Ordering is possible."); }}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ-1386 Play on Words 有向图欧拉通路判定的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。