1.0 并查集概念

对于具有传递性质、联通集合的题目可以考虑并查集。

1.1 并查集模板

声明：以下模板来自于 https://xuq7bkgch1.feishu.cn/docx/CAbedNJ5KobvinxdyKgcKsrlnrd。

有n个数，编号是 1~n，最开始每个数各自在一个集合中,

现在要进行 m 个操作，操作共有两种:
1. M a b，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作;

2. Q a b，询问编号为a和b的两个数是否在同一个集合中;

输入格式
第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 m a b 或 q a b 中的一种。

输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果a和b在同一集合内，则输出 Yes，否则输出 No
每个结果占一行。

数据范围
1 ≤n,m ≤ 10⁵

in:

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

out:

Yes
No
Yes

import java.util.Scanner;

public class Main {
    static int N = 100010;
    static int[] p = new int[N];
    static int n, m;

    static int find(int x) {// 没有做路径压缩
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    static void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            p[pa] = pb;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        for (int i = 1; i <= n; i++) p[i] = i;
        while (m-- > 0) {
            String ch = scanner.next();
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if (ch.equals("M")) {
                merge(a, b);
            } else {
                if (find(a) == find(b)) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
}

离散化并查集模版

如果数据范围改为1 ≤n,m ≤ 10⁹      应该如何处理？

import java.util.HashMap;
import java.util.Scanner;

public class Main {
　　//{x,p[x]}
    static HashMap<Integer, Integer> p = new HashMap<>();
    static int n, m;

    static int find(int x) {
        if (!p.containsKey(x)) return x;
        p.put(x, find(p.get(x)));
        return p.get(x);
    }

    static void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            p.put(pa, pb);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        while (m-- > 0) {
            String ch = scanner.next();
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if (ch.equals("M")) {
                merge(a, b);
            } else {
                if (find(a) == find(b)) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
}

20240410华为实习第一场

题目描述

小明要根据图片的相似度对图片进行分类。他通过一个N*N的矩阵M来表示任意两张图片的相似度，其中M[i][j]表示第i张图片和第j张图片的相似度。根据以下规则判断图片的相似类：

1）如果M[i][j] > 0，则认为第i张图片和第j张图片相似。
2）若A和B相似，B和C相似，但A和B不相似，则A和C间接相似，可以将A、B、C归为一类，但不考虑AC的相似度。
3）若A与所有其他图片不相似，则A被归为自己的一类，相似度总和为0。

请按照相似类的相似度总和从大到小的顺序返回每个相似类中所有图片的相似度之和。

输入
第一行一个数N，代表矩阵M中有N个图片。下面跟着N行，每行有N列数据，空格分隔(为了显示整齐，空格可能为多个)，代表N个图片之间的相似度。

约束:
1. 0<N<=900
2. 0<=M[i][j]<=100,输入保证M[i][j]=0,M[i][j]=M[j][i]

3. 输入的矩阵中分隔符为1个或连续多个空格
输出
每个相似类的相似度之和。格式为:一行数字，分隔符为1个空格

样例1
输入

5
0 0 50 0 0
0 0 0 25 0
50 0 0 0 15
0 25 0 0 0
0 0 15 0 0

输出　

65 25

说明
把1~5看成A,B,C,D，E
矩阵显示，A和C相似度为50，C和E的相似度为15，B和D相似度为25。
划分出2个相似类，分别为
1.{A,C,E}，相似度之和为65
2.{B,D}，相似度之和25
排序输出相似度之和，结果为: 65 25

思路：并查集，遍历每个联通分量/2收集权值。

package com.coedes.union_and_find.huawei20240410;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

/**
 * @description：https://i.cnblogs.com/posts/edit;postId=18152280#postBody
 * @author： wenLiu
 * @create： 2024/4/23 12:25
 */
public class Main {
    static final int N = 910;
    //p : parent[]  v : 存储当前节点作为父节点子树的权重
    static int[] p = new int[N], v = new int[N];

    static int find(int x) {
        if (p[x] != x) return p[x] = find(p[x]);
        return x;
    }

    static void merge(int x, int y, int val) {
        int root_x = find(x);
        int root_y = find(y);
        if (root_y != root_x) {
            p[root_x] = root_y;
            v[root_y] = v[root_x] + val;
        } else {
            v[root_y] += val;
        }
    }

    static void init(int n) {
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        init(n);
        int[][] M = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] s = reader.readLine().split(" ");
            for (int j = 0; j < s.length; j++) {
                int inputVal = Integer.parseInt(s[j]);
                M[i][j] = inputVal;
                if (inputVal > 0) {
                    merge(i, j, inputVal);
                }
            }
        }
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (p[i] == i) res.add(v[i] >> 1);
        }
        Collections.sort(res);
        for (int i = res.size()-1; i >= 0; i--) {
            if (i == res.size() - 1) {
                System.out.print(res.get(i)+" ");
            } else {
                System.out.print(res.get(i));
            }
        }
    }
}

2024美团-人际关系