python/TangDou/AcWing/EulerPath/P3520_2.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10, M = 2e6 + 10;

// 标准错误答案@！
// #2162. 「POI2011 R2 Day1」垃圾运输 Garbage
// https://loj.ac/s/1857935

// 并查集
int p[N], sz[N];
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int d[N];

vector<int> res[N];
int rl;

int st[M];

void dfs(int u) {
    for (int i = h[u]; ~i; i = h[u]) {
        h[u] = ne[i];
        if (st[i]) continue;
        st[i] = st[i ^ 1] = 1;
        int v = e[i];
        dfs(v);
        cout << u << " ";
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P3520.in", "r", stdin);
#endif
    memset(h, -1, sizeof h);
    int n, m;
    scanf("%d %d", &n, &m);

    // 初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;

    int a, b, s, t;
    while (m--) {
        scanf("%d %d %d %d", &a, &b, &s, &t);
        if (s ^ t) {
            add(a, b), add(b, a);
            d[a]++, d[b]++;
            // 并查集
            int pa = find(a), pb = find(b);
            if (pa != pb) {
                p[pb] = pa;
                sz[pa] += sz[pb]; // 维护家庭人员数量
            }
        }
    }

    for (int i = 1; i <= n; i++)
        if (d[i] % 2) {
            puts("NIE");
            exit(0);
        }

    // 肯定是存在欧拉回路,现在是几个环呢？可以用并查集提前处理出来

    // 从头到尾，看一下有多少个家庭，就是有多少个环
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] && i == p[i]) cnt++;
    cout << cnt << endl;

    for (int i = 1; i <= n; i++)
        if (d[i] && i == p[i]) {
            cout << sz[i] << " " << i << " ";
            dfs(i);
            cout << endl;
        }
    return 0;
}