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];
 }
 }
}