题解 | #小团的配送团队#

#include<bits/stdc++.h>
//并查集+dfs图论
using namespace std;
int n, m;
#define MAXN ((int)1e4+5)
vector<int> son[MAXN];
int f[MAXN];
int cnt;

int find(int x) {
    while (f[x] != x)x = f[x] = f[f[x]];
    return x;
}

void init() {
    for (int i = 1; i <= n; ++i)f[i] = i;
}

void unity(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        cnt -= 1;
        if (fx < fy) {
            f[fy] = fx;
            son[fx].push_back(fy);
        } else {
            son[fy].push_back(fx);
            f[fx]=fy;
        }
    }
}


void dfs(vector<int> &path, int idx) {
    for (int i = 0; i < son[idx].size(); ++i) {
        path.push_back(son[idx][i]);
        dfs(path, son[idx][i]);
    }
}

void solve(int idx) {
    vector<int> path;
    path.push_back(idx);
    for (int i = 0; i < son[idx].size(); ++i) {
        path.push_back(son[idx][i]);
        dfs(path, son[idx][i]);
    }
    sort(path.begin(), path.end());
    for (int i = 0; i < path.size(); ++i) {
        cout << path[i] << " ";
    }
    cout << "\n";
}


int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    cnt = n;
    init();
    for (int i = 0; i < m; ++i) {
        int t1, t2;
        cin >> t1 >> t2;
        unity(t1, t2);
    }
    cout << cnt << endl;
    for (int i = 1; i <= n; ++i) {
        if (f[i] == i) {
            solve(i);
        }
    }
    return 0;
}