[UVA] 10129 - Play on words

本題的要求是確認是否為有向的連通圖
運用了尤拉圖概念
先判定各字母節點的入度與出度
僅有兩個節點的入度會不等於出度(起點和終點)
DFS確認是否連通

程式碼參考《入門經典》一書，及CSDN網友shuangde800 的部落格

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
int N;
int G[100][100];
int in[100];
int out[100];
int visit[100];    //visited or not
int dfs(int a);
int main(){
    freopen("input.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
      memset(in,0,sizeof(in));
      memset(out,0,sizeof(out));
      memset(G,0,sizeof(G));
      scanf("%d",&N);
      while(N--){
        string input;
        cin >> input;
        out[input[0]-'a']++;
        in[input[input.size()-1]-'a']++;
        G[input[0]-'a'][input[input.size()-1]-'a']++;
      }
      int cnt1=0,cnt2=0;
      int ok=1;
      //找出入度不等於出度的節點
      for(int i=0;i<100;i++){
        if(!ok)break;
        if(in[i]!=out[i]){
          if(in[i]==out[i]+1)cnt1++;
          else if(out[i]==in[i]+1)cnt2++;
          else {
            ok=0; break;
          }
        }
      }
      //判別是否只有兩個節點入度與出度不同
      if(cnt1 && cnt2 && cnt1+cnt2>2)ok=0;
  
      if(ok){
        memset(visit,0,sizeof(visit));
        for(int i=0;i<100;i++)
          if(out[i]){ //找到出發點，開始DFS
            dfs(i);
            break;
          }
        int ok2=1;
        for(int i=0;i<100;i++){
          if(in[i] && !visit[i]){ok2=0; break;}
          if(out[i] && !visit[i]){ok2=0; break;}
        }
        if(ok2){
          printf("Ordering is possible.\n");
        }
        else printf("The door cannot be opened.\n");
      }
      else printf("The door cannot be opened.\n");
                   
    }
    return 0;
}

//DFS確認是否連通
int dfs(int a){
    visit[a]=1;
    for(int i=0;i<100;i++){
        if(G[a][i] && !visit[i]){
          dfs(i);
        }
    }
}