Uva 10129 - Play on Words 單詞接龍 歐拉道路應用

跟Uva 10054很像，不過這題的單詞是不能反向的，所以是有向圖，判斷歐拉道路。

關於歐拉道路（from Titanium大神）：

判斷有向圖是否有歐拉路
1.判斷有向圖的基圖（即有向圖轉化為無向圖）連通性，用簡單的DFS即可。如果圖都不連通，一定不存在歐拉路
2.在條件1的基礎上
  對於歐拉回路，要求苛刻一點，所有點的入度都要等於出度，那麼就存在歐拉回路了
  對於歐拉道路，要求松一點，只有一個點，出度比入度大1，這個點一定是起點； 一個點，入度比出度大1，這個點一定是終點.其余點的出度等於入度
 （注意，只能大1，而且這樣的點分別只能有1個,而且存在起點就一定要存在終點，存在終點就一定要存在起點）

他用判斷連通性用的是DFS，我用的是並查集實現。

然後判斷為歐拉回路（入度=出度）或者歐拉道路（出入度相差1的點只有不同的兩個）（而且其他點出度=入度！）。

代碼：

 
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
const int maxn = 30; 
int f[maxn], g[maxn][maxn], id[maxn], od[maxn]; 
int t, n, root; 
 
int Find(int x) { 
    if (x != f[x])  
        return f[x] = Find(f[x]); 
    return x; 
} 
 
int main () { 
    scanf("%d", &t); 
    while (t--) { 
        char word[1001]; 
        scanf("%d", &n); 
        for (int i = 0; i < maxn; i++) { 
            f[i] = i; 
            id[i] = 0; 
            od[i] = 0; 
            for (int j = 0; j < maxn; j++) 
                g[i][j] = 0; 
        } 
        for (int i = 0; i < n; i++) { 
            scanf("%s", word); 
            int a = word[0] - 'a', b = word[strlen(word) - 1] - 'a'; 
            g[a][b]++; 
            od[a]++; 
            id[b]++; 
            f[Find(a)] = Find(b); 
            root = Find(b); 
        } 
        int i, ans = 0, flag = 1, in = 0, on = 0; 
        for (i = 0; i < maxn; i++) 
        if (id[i] || od[i]) { 
            if (Find(f[i]) != root) 
                ans++; 
            if (id[i] - od[i] == 1) 
                in++; 
            else if (od[i] - id[i] == 1) 
                on++; 
            else if (abs(id[i] - od[i]) > 1) 
                break; 
        } 
//      printf("%d %d %d %d\n", i, ans, in, on);  
        if (i < maxn || ans > 0 || in > 1 || on > 1) 
            printf("The door cannot be opened.\n"); 
        else 
            printf("Ordering is possible.\n"); 
    }//while  
    return 0; 
} 

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int maxn = 30;
int f[maxn], g[maxn][maxn], id[maxn], od[maxn];
int t, n, root;

int Find(int x) {
 if (x != f[x])
  return f[x] = Find(f[x]);
 return x;
}

int main () {
 scanf("%d", &t);
 while (t--) {
  char word[1001];
  scanf("%d", &n);
  for (int i = 0; i < maxn; i++) {
   f[i] = i;
   id[i] = 0;
   od[i] = 0;
   for (int j = 0; j < maxn; j++)
    g[i][j] = 0;
  }
  for (int i = 0; i < n; i++) {
   scanf("%s", word);
   int a = word[0] - 'a', b = word[strlen(word) - 1] - 'a';
   g[a][b]++;
   od[a]++;
   id[b]++;
   f[Find(a)] = Find(b);
   root = Find(b);
  }
  int i, ans = 0, flag = 1, in = 0, on = 0;
  for (i = 0; i < maxn; i++)
  if (id[i] || od[i]) {
   if (Find(f[i]) != root)
    ans++;
   if (id[i] - od[i] == 1)
    in++;
   else if (od[i] - id[i] == 1)
     on++;
   else if (abs(id[i] - od[i]) > 1)
    break;
  }
//  printf("%d %d %d %d\n", i, ans, in, on);
  if (i < maxn || ans > 0 || in > 1 || on > 1)
   printf("The door cannot be opened.\n");
  else
   printf("Ordering is possible.\n");
 }//while
 return 0;
}