题目1

题目链接：947. 移除最多的同行或同列石头

解题思路

  1. 维护两个哈希表，用来记录某行或某列遇到的第一块石头，key记录某行，value记录石头编号
  2. 遍历石头数组，如果这块石头不在行哈希表中，将其放入行哈希表，如果在，将其与行哈希表中的石头合并，列同理
  3. 遍历完后，移除的石头数量等于原先石头数减去现在集合数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public static int MAXN = 1001;
    public static int[] father = new int[MAXN];
    public static int sets;
    // key:某行 value：编号
    public static HashMap<Integer,Integer> rowFirst = new HashMap<>();//存放某行的第一块石头
    public static HashMap<Integer,Integer> colFirst = new HashMap<>();//存放某列的第一块石头
    public int removeStones(int[][] stones) {
       int n = stones.length;
       build(n);
       for(int i = 0;i < n;i++){
        int x = stones[i][0];
        int y = stones[i][1];
        if(!rowFirst.containsKey(x)){
            rowFirst.put(x,i);
        }else{
            union(i,rowFirst.get(x));
        }
        if(!colFirst.containsKey(y)){
            colFirst.put(y,i);
        }else{
            union(i,colFirst.get(y));
        }
       }    
       return n - sets;
    }
    public static void build(int n){
        rowFirst.clear();
        colFirst.clear();
        for(int i = 0;i < n;i++){
            father[i] = i;
        }
        sets = n;
    }
     public static int find(int i){
        if(i != father[i]){
            father[i] = find(father[i]);
        }
        return father[i];
    }
    public static void union(int i,int j){
        int fi = find(i);
        int fj = find(j);
        if(fi != fj){
            father[fi] = fj;
            sets--;//合并集合数减1
        }
    }
}

题目2

题目链接：2092. 找出知晓秘密的所有专家 - 力扣（LeetCode）

解题思路

  1. 维护一个secret数组，用来记录以某个节点为代表元素的集合是否知道秘密，初始化时只有0和firstPerson知道秘密
  2. 将会议数组按会议开始时间从小到大排序，找出在同一时刻开始的会议
  3. 将所有专家进行union,最终知道秘密的专家和不知道秘密的专家会被放入两个集合
  4. 将不知道秘密的专家集合拆散
  5. 到第二个时刻重复上述操作
  6. 最终遍历所有专家，若其所在连通分量的根知道秘密，则加入答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public static int MAXN = 100001;
    public static int[] father = new int[MAXN];
    public static boolean[] secret = new boolean[MAXN];//记录某个专家是否知道秘密
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        int m = meetings.length;//m场会议
        Arrays.sort(meetings,(a,b)->(a[2] - b[2]));
        build(n,firstPerson);
        for(int l = 0,r;l < m;){
            r =  l;
            while(r+1<m && meetings[r][2] == meetings[r+1][2]){//找到在同一时刻开会的所有专家
                r++;
            }
            //范围时（l，r），不是（0,r）
            for(int i = l;i <= r;i++){//将知道秘密的专家和不知道秘密的专家分别合并
                union(meetings[i][0],meetings[i][1]);
            }
            for(int i = l;i <= r;i++){
               int a = meetings[i][0];
               int b = meetings[i][1];
               if(!secret[find(a)]){
                father[a] = a;
               }
                if(!secret[find(b)]){
                father[b] = b;
               }
            }
            l = r + 1;
        }
        List<Integer> ans = new ArrayList<>();
        for(int i = 0;i < n;i++){
            if(secret[find(i)]){
                ans.add(i);
            }
        }
        return ans;
    }
    public static void build(int n ,int firstPerson){
        for(int i = 0;i < n;i++){
            father[i] = i;
            secret[i] = false;//初始时所有人都不知道秘密
        }
        father[firstPerson] = 0;
        secret[0] = true;//0和firstPerson在0时刻知道秘密，放入同一个集合
    }
    public static int find(int i){
        if(i != father[i]){
            father[i] = find(father[i]);
        }
        return father[i];
    }
    public static void union (int x,int y){
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            father[fx] = fy;
            secret[fy] |= secret[fx];
        }
    }
}

题目3

题目链接：2421. 好路径的数目

解题思路

  1. 初始化
    • 每个节点独立成一个集合；
    • maxcnt[i] = 1：表示以 i 为根的集合中，最大值（即 vals[i]）出现的次数为 1；
    • **初始答案 **ans = n（每个节点自身是一条好路径）。
  2. 对边排序
    • **按 **max(vals[u], vals[v]) 升序排序。
    • 这确保我们在处理某条边时，其两端的节点值都不超过当前“激活阈值”。
  3. 依次处理每条边
    • **找到两个端点所在集合的根 **fx, fy；
    • **比较 **val[fx]和vals[fy]
      • 若不等：将较小值的集合合并到较大值的集合（保留更大值作为新根）；
      • **若相等：说明两个集合的最大值相同，此时新增好路径数 = **maxcnt[fx] * maxcnt[fy]，然后合并，并更新 maxcnt。
  4. 返回总路径数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public static int MAXN = 30001;
    public static int[] father = new int[MAXN];
    public static int[] maxcnt = new int[MAXN];//记录每个集合出现最大值的次数
    public int numberOfGoodPaths(int[] vals, int[][] edges) {
        int n = vals.length;
        build(n);
        int ans = n;
        Arrays.sort(edges,(e1,e2) -> (Math.max(vals[e1[0]],vals[e1[1]]) - 
                                      Math.max(vals[e2[0]],vals[e2[1]])));
        for(int[] edge: edges){
            ans += union(edge[0],edge[1],vals);
        }
        return ans;
    }
    public static void build(int n){
        for(int i = 0;i < n;i++){
            father[i] = i;
            maxcnt[i] = 1;
        }
    }
    public static int find(int i){
        if(i != father[i]){
            father[i] = find(father[i]);
        }
        return father[i];
    }
    //返回好路径条数
    public static int union(int x,int y,int[] vals){
        int fx = find(x);
        int fy = find(y);
        int path = 0;
        if(vals[fx] > vals[fy]){
            father[fy] = fx;
        }else if(vals[fy] > vals[fx]){
            father[fx] = fy;
        }else{//最大值相等
            path = maxcnt[fx] * maxcnt[fy];//路径数
            father[fx] = fy;
            maxcnt[fy] += maxcnt[fx];//更新最大值个数
        }
        return path;
    }
}

题目4

解题思路

  1. 第一步：预处理
  • **标记所有 **initial 节点为“病毒节点”。
  • **初始化并查集，**只用于普通节点（病毒节点不参与合并）。
  1. 第二步：合并普通节点
  • **遍历所有边，**仅当两个端点都是普通节点时才合并。
  • 得到若干个纯净的普通连通分量，每个分量有：
    • 代表元（根）
    • 大小（size[root]）
  1. 第三步：标记每个分量的感染源

  • **对每个病毒节点 **

    1
    sick ∈ initial

    • **遍历其所有邻居 **neighbour；

    • **若 **neighbour是普通节点且与 sick相连：

    • **找到 **neighbour 所在分量的根 root；

    • 标记该分量的感染源：

      • **若首次被感染 → 记录 **infect[root] = sick；
      • **若已有一个不同感染源 → 标记为 **infect[root] = -2（多源，无法拯救）。

**4.**第四步：统计拯救收益

  • 对每个普通连通分量（仅看代表元）：
    • **若 **infect[root] >= 0（唯一感染源），
    • **则 **cnts[infect[root]] += size[root]。

**5.**第五步：选择最优删除节点

  • **在 **initial 中，选择 cnts[x] 最大的 x；
  • **若相同，选编号最小的（先排序 **initial 即可保证）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
    public static int MAXN = 301;
    public static int[] cnts = new int[MAXN];//删除病毒可以拯救多少个节点
    public static int[] size = new int[MAXN];//普通点连接的集合大小
    public static boolean[] virus = new boolean[MAXN];//哪些点是病毒
    public static int[] father = new int[MAXN];
    public static int[] infect = new int[MAXN]; //infect[a] == -1表示无感染源 
    // == -2 表示有多个感染源，无法拯救 >= 0表示只有一个感染源，可以拯救
​
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        build(n, initial);
        //将连接的普通点合并
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1 && !virus[i] && !virus[j]) {
                    union(i, j);
                }
            }
        }
        //给普通点集合设置感染源
        for (int sick : initial) {
            for (int neighbour = 0; neighbour < n; neighbour++) {
                if (sick != neighbour && !virus[neighbour] && graph[sick][neighbour] == 1) {
                    int a = find(neighbour);//集合的代表节点
                    if (infect[a] == -1) {
                        infect[a] = sick;//只有当还没变成多源，并且来了一个不同的感染源，我才把它变成多源
                    } else if (infect[a] != -2 && infect[a] != sick) {
                        infect[a] = -2;
                    }
                }
            }
        }
        //统计拯救数据
        for (int i = 0; i < n; i++) {
            //只看代表点
            if (i == find(i) && infect[i] >= 0) {
                cnts[infect[i]] += size[i];
            }
        }
        Arrays.sort(initial);
        int ans = initial[0];
        int max = cnts[ans];
        for (int i : initial) {
            if (cnts[i] > max) {
                ans = i;
                max = cnts[i];
            }
        }
        return ans;
    }
​
    public static void build(int n, int[] initial) {
        for (int i = 0; i < n; i++) {
            cnts[i] = 0;
            size[i] = 1;
            virus[i] = false;
            father[i] = i;
            infect[i] = -1;
        }
        for (int i : initial) {
            virus[i] = true;
        }
    }
​
    public static int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }
​
    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
            size[fy] += size[fx];
        }
    }
}