poj 1386(有向图判欧拉路+并查集)

poj 1386
题意：给出几个字符串问能否首位相接成一个环或者一条链。

就是判有向图是否存在欧拉路即可。

欧拉路存在条件(图连通)：
有向图：有一个点入度等于出度加一，有一个点出度等于入度加一，其余所有点入度等于出度
欧拉回路存在条件(图连通)：
有向图：所有点入度等于出度

用并查集维护一下就好。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int en, n, ino[35], outo[35], f[35];
char s[1005];
struct edge {
    int v, vis;
}ed[200000 + 5];
vector<int> G[35];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
void ins(char x, char y) {
    ed[++en] = (edge){y - 'a', 0};
    G[x - 'a'].push_back(en);
    ino[y - 'a']++, outo[x - 'a']++;
    int u = find(x - 'a'), v = find(y - 'a');
    if (u != v) f[u] = v;
}
void clean() {
    en = 0;
    for (int i = 0; i <= 30; i++) G[i].clear(), f[i] = i, ino[i] = outo[i] = 0;
}
int solve() {
    scanf("%d", &n);
    clean();
    for (int i = 0; i < 26; i++) f[i] = i;
    for (int i = 1; i <= n; i++) scanf("%s", s), ins(s[0], s[strlen(s) - 1]);
    for (int i = 0; i < 26; i++) find(i);
    int ans = 0;
    for (int i = 0; i < 26; i++) ans += (f[i] == i && (ino[i] || outo[i]));
    if (ans != 1) return cout << "The door cannot be opened." << endl, 0;
    int st = -1, ed = -1, fl = 0;
    for (int i = 0; i < 26; i++) {
        if (ino[i] != outo[i]) {
            fl = 1;
            if (ino[i] == outo[i] + 1) {
                if (ed >= 0) return cout << "The door cannot be opened." << endl, 0;
                ed = i;
            } else if (ino[i] == outo[i] - 1) {
                if (st >= 0) return cout << "The door cannot be opened." << endl, 0;
                st = i;
            } else return cout << "The door cannot be opened." << endl, 0;
        }
    }
    if ((st == -1 || ed == -1) && fl) return cout << "The door cannot be opened." << endl, 0;
    return cout << "Ordering is possible." << endl, 0;
    return 0;
}
int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}