单词 Play on Words

原题链接

题解

我们将一个单词的首字母和尾字母看成两个结点，每个单词代表一条有向边。

此时题意为：给你一个有向图，让你找到一条路径，使得仅仅只经过每条边一次。

那么题意就是让我们求一个有向图的欧拉回路。

code

#include<bits/stdc++.h>
using namespace std;
int father[30],in[30],out[30];
void build(){
    for (int i=1;i<=26;i++){
        father[i]=i;
        in[i]=0;
        out[i]=0;
    }
}
int one;
int find(int x){
    if (father[x]!=x) father[x]=find(father[x]);
    return father[x];
}
void input(int n){
    for (int i=1;i<=n;i++){
        string s;
        cin>>s;
        int len=s.size();
        out[s[0]-'a'+1]++;
        in[s[len-1]-'a'+1]++;
        int fx=find(father[s[0]-'a'+1]),fy=find(father[s[len-1]-'a'+1]);
        if (fx!=fy) father[fx]=fy;
        one=s[0]-'a'+1;
    }
}
bool Fleury(){
    int n1=0,n2=0;
    for (int i=1;i<=26;i++){
        if (in[i]==out[i] && in[i]==0) continue;
        if (in[i]-out[i]==1) {
            n1++;
            if (n1>1) return false;
            continue;
        }
        if (out[i]-in[i]==1){
            n2++;
            if (n2>1) return false;
            continue;
        }
        if (in[i]!=out[i]) return false;
        if (find(father[i])!=one) return false;
    }
    return true;
}
int main(){
    int t;
    cin>>t;
    while (t--){
        build();
        int n;
        cin>>n;
        input(n);
        one=find(father[one]);
        if (Fleury()) cout<<"Ordering is possible.\n";
        else cout<<"The door cannot be opened.\n";
    }
    return 0;
}