欧拉回路 试读

思路

首先欧拉回路是一个连通图，这个可以用并查集的模板来写，下面详尽的写了并查集的一个模板，具体关于并查集的知识我就不叙述了。

然后还要满足所有顶点的度为偶数，这个因为已经给出了各条边，很容易求出来度数

其中需要注意以下几点：

• 自环不用算，因为去掉自环也不会产生影响，但是加上自环的话会让度数计算产生问题。
• 孤立点不用算，也就是度为 0 的点，孤立点首先不会对欧拉回路产生影响，但是却会增加连通分支数量。
• 代码尽管很长，但是前面一半都是一个并查集模板类，main 函数中的代码前面一半也只是做了一个初始化的工作，后面一半就是判断是否连通分量为 1 以及是否度均为偶数。

#include<iostream>
#include<vector>
#include<numeric>

using namespace std;

class UF {
public:
    vector<int> fa;
    vector<int> sz;
    int comp_cnt; // 连通分量数目
    int n;
public:
    UF(int _n) : n(_n), comp_cnt(_n), fa(_n), sz(_n, 1){
        iota(fa.begin(), fa.end(), 0);
    }

    int findFa(int x){
        return x == fa[x] ? x : fa[x] = findFa(fa[x]);
    }

    void unite(int x, int y){
        x = findFa(x);
        y = findFa(y);
        if(x == y) return;
        if(sz[x] < sz[y]) swap(x, y);
        fa[y] = x;
        sz[x] += sz[y];
        comp_cnt --;
    }

    bool connected(int x, int y) {
        x = findFa(x);
        y = findFa(y);
        return x == y;
    }
};

int main(){
    int N, M;
    while(cin >> N && N){
        cin >> M;
        vector<int> degree(N, 0);
        UF uf(N);
        int x, y;
        for(int i = 0; i < M; i ++){
            cin >> x >> y;
            // 去掉自环
            if(x == y) continue;
            uf.unite(x - 1, y - 1);
            degree[x - 1] ++;
            degree[y - 1] ++;
        }
        // 去掉孤立点也就是度为 0 的点
        for(int d : degree)
            if(d == 0) uf.comp_cnt --;
        // 连通分量数目不为 1
        if(uf.comp_cnt != 1) cout << 0 << endl;
        else{
            // 检查是否存在度为奇数的点
            bool flag = true;
            for(int d : degree)
                if(d % 2){
                    flag = false;
                    cout << 0 << endl; break;
                }
            if(flag) cout << 1 << endl;
        }
    }
}