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

#include<bits/stdc++.h>
using namespace std;

int find(vector<int>&father, int x) {
    if (father[x] == x)return x;
    else return find(father, father[x]);
}

void merg(vector<int>& father, vector<int>& rank, int x, int y) {
    int X = find(father, x);
    int Y = find(father, y);
    if (X != Y) {
        if (rank[X] > rank[Y]) father[Y] = X;
        else if (rank[X] < rank[Y]) father[X] = Y;
        else {
            father[X] = Y;
            rank[Y]++;
        }
    }
}

/*fa[1] = 2, fa[2] = 2, fa[3] = 1, fa[4] = 2, fa[5] = 2;
}*/
int main() {
    int n, m;
    cin >> n >> m;
    vector<int>father(n + 1);
    vector<int>rank(n + 1);
    for (int i = 1; i <= n; ++i) { 
        father[i] = i; 
        rank[i] = 1;
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        merg(father, rank,a, b);
    }
    /*vector<int>xiaoqu;
    for (int i = 1; i <= n; ++i) {
        if (father[i] == i) xiaoqu.emplace_back(i);
    }
    cout << xiaoqu.size() << endl;*/
    map<int, vector<int>>mp;
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        father[i] = find(father, i);//对父集合重新赋值，将i最终的根节点赋为它的父节点
        if(mp[father[i]].size() == 0) cnt++;
        mp[father[i]].emplace_back(i);//将父节点相同的i存入同一数组，获取同一集合的所有编号
    }
    cout << cnt << endl;

    map<int, int>smp;//smp[每个集合中最小的小区编号] = mp中每个小区的索引key值
    for (auto& [ignor, tem] : mp) smp[tem[0]] = ignor;//对每个集合中最小的值进行排序

    for (auto& [ignor, tem] : smp) {//按照每个小区最小值从小到大依次输出相同小区的订单号
        vector<int>ort = mp[tem];
        cout << ort[0];
        for (int i = 1; i < ort.size(); ++i)cout << " " << ort[i];
        cout << endl;
    }
    return 0;

}