小团的配送团队

n, order = list(map(int, input().split()))
temp = [i for i in range(n+1)]
group = dict(zip(temp, [[i] for i in range(n+1)]))
for _ in range(order):
    pair = list(map(int, input().split()))
    if temp[pair[0]] < temp[pair[1]]:
        group[temp[pair[0]]] += group[temp[pair[1]]]
        wait = temp[pair[1]]
        for i in group[temp[pair[1]]]:
            temp[i] = temp[pair[0]]
        group.pop(wait)
    elif temp[pair[0]] > temp[pair[1]]:
        group[temp[pair[1]]] += group[temp[pair[0]]]
        wait = temp[pair[0]]
        for i in group[temp[pair[0]]]:
            temp[i] = temp[pair[1]]
        group.pop(wait)
data = list(group.items())
data.sort(key=lambda x:x[0])
print(len(data)-1)
for each in data[1:]:
    ans = each[1]
    ans.sort()
    print(" ".join(map(str,ans)))

import java.util.*;
public class Main {
    public static void main(String[] args) {
        //n为订单数量，m为数量关系
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        UF uf = new UF(n+1);
        for(int i = 0; i < m; i++) {
            uf.union(sc.nextInt(), sc.nextInt());
        }
        //遍历[1, n] 用visited保证只访问一次
        boolean[] visited = new boolean[n+1];
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        for(int i = 1; i <= n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                for(int j = i+1; j <= n; j++){
                    if(!visited[j] && uf.isConnect(i, j)) {
                        visited[j] = true;
                        list.add(j);
                    }
                }
                ans.add(list);
            }
        }
        System.out.println(ans.size());
        for(int i = 0; i < ans.size(); i++) {
            ArrayList<Integer> list = ans.get(i);
            for(int j = 0; j < list.size(); j++)
                System.out.print(list.get(j) + " ");
            System.out.print("\n");
        }
    }

    static class UF {
        public int[] parents;
        public UF(int n) {
            parents = new int[n];
            for(int i = 0; i < n; i++) parents[i] = i;
        }
        public int find(int i) {
            if(parents[i] != i) {
                parents[i] = find(parents[i]);
            }
            return parents[i];
        }
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            parents[rootI] = rootJ;
        }
        public boolean isConnect(int i, int j) {
            return find(i) == find(j);
        }
    }
}

不理解并查集的可以看看https://zhuanlan.zhihu.com/p/93647900，讲的很清楚明了
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> vec(n + 1), rank(n + 1, 1);
    for (int i = 1; i < n + 1; ++i)
        vec[i] = i;

    function<int(int)> find = [&](int x) -> int
    {
        return x == vec[x] ? x : (vec[x] = find(vec[x]));
    };

    function<void(int, int)> merge = [&](int i, int j) -> void
    {
        int x = find(i), y = find(j);
        if(rank[x] <= rank[y])
            vec[x] = y;
        else
            vec[y] = x;
        if(rank[x] == rank[y] && x != y)
            ++rank[y];
    };

    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }

    unordered_map<int, set<int>> um;
    for (int i = 1; i < n + 1; ++i)
        um[find(i)].insert(i);

    auto lambda = [](const set<int> &lhs, const set<int> &rhs)
    {
        return *lhs.begin() < *rhs.begin();
    };
    vector<set<int>> vs;
    for (auto &s : um)
        vs.push_back(std::move(s.second));
    sort(vs.begin(), vs.end(), lambda);

    cout << vs.size() << endl;
    for (const auto &s : vs)
    {
        for (const int val : s)
            cout << val << ' ';
        cout << endl;
    }
}

标准并查集做法

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main{
    static int[] root;
    // 小区数
    static int branches;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().trim().split(" ");
        int n = Integer.parseInt(inputs[0]);
        // 已知关系数量
        int m = Integer.parseInt(inputs[1]);
        root = new int[n+1];
        branches = n;
        for(int i=1;i<=n;++i){
            root[i] = i;
        }
        for(int i=0;i<m;++i){
            inputs = br.readLine().trim().split(" ");
            int x = Integer.parseInt(inputs[0]);
            int y = Integer.parseInt(inputs[1]);
            union(x,y);
        }
        for(int i=1;i<=n;++i){
            root[i] = find(i);
        }
        //System.out.println(Arrays.toString(root));
        //System.out.println(branches);
        // <小区代表元素,小区编号>
        Map<Integer,Integer> map = new HashMap<>();
        // 各个小区的订单,按照编号排序
        List<List<Integer>> areas = new ArrayList<>();
        int cnt = 0;
        for(int i=1;i<=n;++i){
            // 如果出现一个新的root，表示出现了一个新的小区,给小区编号，且这个root就是该小区最小的订单号
            // 并增加一个list到小区列表中
            if(!map.containsKey(root[i])){
                map.put(root[i],cnt);
                cnt++;
                areas.add(new ArrayList<>());
            }
            int num = map.get(root[i]);
            areas.get(num).add(i);
        }
        System.out.println(branches);
        // 因为是按顺序处理的订单，所以结果已经有序，直接输出
        for(List<Integer> list:areas){
            for(int t:list){
                System.out.print(t+" ");
            }
            System.out.println();
        }
    }

    public static int find(int x){
        return x == root[x]?x:(root[x] = find(root[x]));
    }

    public static void union(int x,int y){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX!=rootY){
            root[rootX] = rootY;
            branches--;
        }
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
int parents[10000];
 
void init(int n) {
    for (int i = 1; i <= n; ++i) {
        parents[i] = i;
    }
}
 
int find(int x) {
    return x == parents[x] ? x : (parents[x] = find(parents[x]));
}
 
void comb(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
        return;
    } else if (x > y) {
        comb(y, x);
    } else {
        parents[y] = x;
    }
}
 
int main() {
    int m, n;
    cin >> m >> n;
    init(n);
    while (m--) {
        int a, b;
        cin >> a >> b;
        comb(a, b);
    }
    int cnt = 0;
    map<int, vector<int>> mp;
    for (int i = 1; i <= n; ++i) {
        parents[i] = find(i);
        if (mp[parents[i]].size() == 0) {
            ++cnt;
        }
        mp[parents[i]].emplace_back(i);
    }
    cout << cnt << endl;
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        vector<int> tmp = it->second;
        cout << tmp[0];
        for (int i = 1; i < tmp.size(); ++i) {
            cout << ' ' << tmp[i];
        }
        cout << endl;
    }
     
    return 0;
}