欧拉回路

欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？
https://blog.csdn.net/csyifanZhang/article/details/105767883
↑更好的阅读体验

之前刷图论的题没有玩过欧拉回路，但是他的判定方法稍加讨论就可以得出

对无向图而言，如果一个点相连接的边是奇数个会怎样？==他要么无法返回原点，要么总有一条边我们无法经过==，最简单的情况就是下图，如果存在度为1的节点，那么只能进不能出，或者只能出不能返回，显然不存在欧拉回路。右图存在度为3的节点，如果我们从B开始，B到c要么选择1，要么选择2，永远不可能走完1和2和其余的边再回到B。

当然我们还要考虑图可能是不连通的，可能有孤立点这样的情况，如下图，孤立点对欧拉回路是没有影响的，因为没有边和他相连。而如果这个图有多个连通分量，此时显然不存在欧拉回路，也就是说，除了孤立节点外，其它节点满足 1.连通 2.度为偶数

对于有向图，无非将度分为了出度和入度，如果出度等于入度，那么一个点的边才有可能全部被走完。

ll kind[MAX], degree[MAX];
ll find(ll k) {
    if (k == kind[k])return k;
    else return kind[k] = find(kind[k]);
}

void unite(ll a, ll b) { kind[find(b)] = kind[find(a)]; }

int main() {
    ll N, M, a, b, l, res = 0;
    while (cin >> N  && N) {
        cin >> M;
        //无向图，不分出度入度
        for (int i = 1; i <= N; i++)G[i].clear(), kind[i] = i, degree[i] = 0;
        for (int i = 1; i <= M; i++) {
            cin >> a >> b; degree[b]++; degree[a]++; unite(a, b); l = a;
        }
        //除了一个连通图之外，其他的点都是孤立点
        //l记录了一个连通图中的一个边
        int i = 1; res = 0;
        for (i = 1; i <= N; i++) {
            if (find(i) != find(l) && degree[i] != 0)break;//不是连通图中的点却有边相连
            else if (degree[i] % 2 != 0)break;//相连的边数目为奇数
        }
        if (i == N + 1)res = 1;
        cout << res << endl;
    }
}