AcWing 1185. 单词游戏

题目传送门

这一题的建图方式和\(AcWing\) \(1165\). 单词环是一模一样的，每个单词看成一条边，首字母和为字母看成图中的顶点。这是一个有向图。

建完图之后，问题就变成了我们能否找到一条路径，依次走过每条边，即该有向图中是否存在欧拉路径？

我们要清楚如何判有向图是否存在欧拉路径，需要满足两个条件：

• 所有的边要连通；

• 除了起点和终点外，其余点的入度必须等于出度；

对于（1），可以使用并查集解决，如果某个点有边相连，但是和并查集不连通，说明边不连通。

本题不需要将所有边存储下来，只需要判断连通性以及记录每个点的入度和出度判断是否存在答案即可。

#include 
using namespace std;

const int N = 2e5 + 10;
int p[N];
int din[N], dout[N];
int st[N];

int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main() {
    int n, T;
    cin >> T;
    while (T--) {
        cin >> n;
        memset(st, 0, sizeof st);
        memset(din, 0, sizeof din);
        memset(dout, 0, sizeof dout);
        for (int i = 0; i <= n; i++) p[i] = i;
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            int a = s[0] - 'a', b = s[s.size() - 1] - 'a';
            st[a] = st[b] = 1; //记录此字符是否在点集中出现过
            dout[a]++, din[b]++;
            p[find(a)] = find(b);
        }
        //是不是存在欧拉路径,默认是存在的，如发现与定理违背，将修改标志
        bool success = true;

        // 1、连通图才有欧拉路径
        //利用并查集检查是不是连通图
        int sign = -1;
        for (int i = 0; i < 26; i++) {
            if (st[i]) {                    //如果这个点出现过
                if (sign == -1)             //如果是首次
                    sign = find(i);         //记录为i家族
                else if (sign != find(i)) { //找到不是一个家族的情况
                    success = false;
                    break;
                }
            }
        }
        // 2、如果入度与出度完全相等有欧拉路径
        //如果存在出度=入度+1(起点) 存在入度=出度+1(终点) 各1个，其它各点出度与入度均一致,也可以有欧拉路径
        int start = 0, ed = 0;
        for (int i = 0; i < 26; i++) {
            if (din[i] != dout[i]) {
                if (dout[i] == din[i] + 1) //可能是起点
                    start++;
                else if (din[i] == dout[i] + 1) //可能是终点
                    ed++;
                else { //入度与出度不等，差还不是1，肯定不存在欧拉路径
                    success = false;
                    break;
                }
            }
        }
        if (start > 1 || ed > 1) success = false;

        if (success)
            cout << "Ordering is possible." << endl;
        else
            cout << "The door cannot be opened." << endl;
    }
}