1202. 交换字符串中的元素-并查集

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class test1202 {
    /**
     * 给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
     */
    public static void main(String[] args) {
        String s="dcab";
        List<List<Integer>> pairs=new ArrayList<>();
        List<Integer> list=new ArrayList<>();
        list.add(0);
        list.add(3);
        pairs.add(new ArrayList<>(list));
        list.clear();
        list.add(1);
        list.add(2);
        pairs.add(new ArrayList<>(list));
        String result=smallestStringWithSwaps(s, pairs);
        int x=0;
    }
    //使用并查集，所谓并查集就是把pair中起点或者终点相同的元素放在一起，并查集内部排序，之后组合就好
    public static String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int []parents=new int[s.length()];
        //初始化每个位置的parent都是他自己
        for(int i=0;i<s.length();i++){
            parents[i]=i;
        }
        //pair中两个点在一个阵营
        for(List<Integer> list:pairs){
            int a=find(list.get(0),parents);
            int b=find(list.get(1),parents);
            parents[a]=b;
        }
        //每个的父节点做key，优先队列里面放对应的char，这样每个parent对应的并查集就排好序了
        Map<Integer,Queue<Character>> map=new HashMap<>();
        for(int i=0;i<s.length();i++){
            int an=find(i,parents);
            map.computeIfAbsent(an, k->new PriorityQueue<>()).offer(s.charAt(i));
        }
        //最后合并起来，得到交换后的结果
        StringBuilder stringBuilder = new StringBuilder();
        for(int i=0;i<s.length();i++){
            Queue q=map.get(find(i,parents));
            stringBuilder.append(q.poll());
        }

        return stringBuilder.toString();
    }
    //查找祖宗节点，只有当前的值等于他父亲节点时候，才是祖宗节点
    public static int find(int i,int []parent){
        if(parent[i]!=i){
            ////如果不是祖宗节点就继续往上查找
            parent[i]=find(parent[i],parent);
        }
        return parent[i];
    }


    
}