并查集

2021-01-20

并查集

1. 并查集介绍

int[] data = new int[10];
public int find(int x){
    if(data[x] == x){
        return x;
    }else{
        data[x] = find(data[x]);
        return data[x];
    }
}

public voif merge(int a, int b){
    int x = find(a);
    int y = find(b);
    if(x != y){
        data[x] = y;
    }
}

2. 典型例题

1202. 交换字符串中的元素

class Solution {
    int data[];
    public int find(int x){
        if (data[x] == x){
            return x;
        }else{
            data[x] = find(data[x]);
            return data[x];
        }
    }
    public void merge(int a, int b){
        int x = find(a);
        int y = find(b);
        if (x != y){
            data[x] = y;
        }
    }
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        // 每一个字母看成是图中的一个节点，每个下标是一个节点  pairs看作是相连的边
        // 如果 [a,b]可交换， [b,c]可交换，那么[a,c]可交换。
        // 将相互连接的字母集合merge，形成若干个连通图 连通图内的字母可以任意交换
        int len = s.length();
        data = new int[len];
        for (int i = 0; i < data.length; i++){
            data[i] = i;
        }
        HashMap<Integer, List<Integer>> map = new HashMap<>();

        for (List<Integer> pair: pairs){
            int a = pair.get(0);
            int b = pair.get(1);
            if (find(a) != find(b)){
                merge(a,b);
            }
        }

        for (int i = 0; i < len; i++){
            int t = find(i);//第i个节点的根节点
            List<Integer> list = map.getOrDefault(t, new ArrayList<Integer>());
            list.add(i);
            map.put(t,list);
        }
        // 同一个连通图内字典序最小排序
        char res[] = new char[len];
        for (Map.Entry entry:map.entrySet()){
             ArrayList<Integer> list = (ArrayList<Integer>) entry.getValue();
             List<Integer> tmp = (List<Integer>) list.clone();
             Collections.sort(list, new Comparator<Integer>() {
                 @Override
                 public int compare(Integer o1, Integer o2) {
                     return s.charAt(o1) - s.charAt(o2);
                 }
             });
            for (int i = 0; i < list.size(); i++){
                int index = list.get(i);
                res[tmp.get(i)] = s.charAt(index);
            }
        }
        return String.valueOf(res);
    }
}

684. 冗余连接

class Solution {
    int data[];
    public int find(int x){
        if (data[x] == x){
            return x;
        }else{
            data[x] = find(data[x]);
            return data[x];
        }
    }
    public void merge(int a, int b){
        int x = find(a);
        int y = find(b);
        if (x != y){
            data[x] = y;
        }
    }
    public int[] findRedundantConnection(int[][] edges) {
        //并查集，思路：针对每一条边进行连接
        int n = edges.length;
        data = new int[n + 1];
        for (int i = 0; i <= n; i++){
            data[i] = i;
        }
        int[] ans = new int[2];
        for (int[] edge:edges){
            int a = edge[0], b = edge[1];
            if (find(a) != find(b)){
                merge(a,b);
            }else{
                ans[0] = a;
                ans[1] = b;
                return ans;
            }
        }
        return new int[]{0,0};
    }
}

990. 等式方程的可满足性

class Solution {
    int data[] = new int[26];
    public int find(int x){
        if (data[x] == x){
            return x;
        }else{
            data[x] = find(data[x]);
            return data[x];
        }
    }
    public void merge(int a, int b){
        int x = find(a);
        int y = find(b);
        if (x != y){
            data[x] = y;
        }
    }
    public boolean equationsPossible(String[] equations) {
        for (int i = 0; i < data.length; i++){
            data[i] = i;
        }
        for (int i = 0; i < equations.length; i++){
            String tmp = equations[i];
            int a = tmp.charAt(0) - 'a', b = tmp.charAt(3) - 'a';
            if (tmp.substring(1,3).equals("==")){
                merge(a, b);
            }
        }
        for (int i = 0; i < equations.length; i++){
            String tmp = equations[i];
            int a = tmp.charAt(0) - 'a', b = tmp.charAt(3) - 'a';

            if (tmp.substring(1,3).equals("!=") && find(a) == find(b)){
                return false;
            }
        }
        return true;
    }
}

3. 最小生成树

利用并查集解决最小生成树问题。

思路：使用克鲁斯卡尔算法（加边）然后利用并查集判断子图是否连通。

```java
import java.util.*;

public class Main{

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int c = in.nextInt();
    int[] data = new int[n+1];
    for (int i = 1; i <= n; i++){
        data[i] = i;
    }
    PriorityQueue<int []> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
    // 最小生成树问题
    for (int i = 0; i < n * (n - 1) / 2; i++){
        int s = in.nextInt();//起点
        int t = in.nextInt();//终点
        int p = in.nextInt();//距离
        queue.add(new int[]{s,t,p*c});
    }
    int ans = 0;
    while (!queue.isEmpty()){
        int[] edge = queue.poll();
        int s = edge[0], t = edge[1];
        if (find(data,s) == find(data,t)){
            continue;
        }
        merge(data,s,t);
        ans += edge[2];

    }
    System.out.println(ans);
}

public static int find(int[] data, int a){
    if (data[a] == a){
        return a;
    }else{
        data[a] = find(data,data[a]);
    }
    return data[a];
}
public static void merge(int[] data, int a, int b){
    int x = find(data,a);
    int y = find(data,b);
    if (x != y){
        data[x] = y;
    }
}

}