package question;



import java.util.*;

public class Question1202 {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        Union union = new Union(s.length());
        for (int i = 0; i < pairs.size(); i++) {
            List<Integer> list = pairs.get(i);
            union.merge(list.get(0), list.get(1));
        }
        Map<Integer, Queue<Character>> map=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            int key = union.find(i);
            if (map.containsKey(key)) {
                if (key!=i)
                    map.get(key).add(s.charAt(i));
            } else {
                Queue<Character> queue = new PriorityQueue<>();
                queue.add(s.charAt(key));
                if (key!=i)
                    queue.add(s.charAt(i));
                map.put(key, queue);
            }
        }
        //map.computeIfAbsent()
        char[] chars = new char[s.length()];
        for (int i = 0; i < chars.length; i++) {
            int key = union.find(i);
            chars[i] = map.get(key).poll();
        }
        return new String(chars);
    }

    private static class Union {
        int[] root;

        public Union(int n) {
            root=new int[n];
            for (int i = 0; i < root.length; i++) {
                root[i]=i;
            }
        }

        public boolean merge(int x, int y) {
            x=find(x);
            y=find(y);
            if (x==y) return true;
            root[x]=y;
            return false;
        }

        public int find(int x) {
            if (root[x]==x) return x;
            root[x]=find(root[x]);
            return root[x];
        }
    }
}