You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.
You can swap the characters at any pair of indices in the given pairs any number of times.
Return the lexicographically smallest string that s can be changed to after using the swaps.
Example 1:
Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"
Example 2:
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"
Example 3:
Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"
Constraints:
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        parent = [i for i in range(n)]
        
        for u, v in pairs:
            self.union(parent, u, v)
        
        m = collections.defaultdict(list)
        for i in range(n):
            m[self.find_root(parent, i)].append(i)
        
        ans = list(s)
        for _, indices in m.items():
            temp = []
            for i in indices:
                temp.append(s[i])
            temp.sort()
            for i in range(len(temp)):
                ans[indices[i]] = temp[i]
        
        return \"\".join(ans)
    
    def find_root(self, parent, x):
        if parent[x] != x:
            parent[x] = self.find_root(parent, parent[x])
        return parent[x]
    
    def union(self, parent, x, y):
        x_root = self.find_root(parent, x)
        y_root = self.find_root(parent, y)
        if x_root != y_root:
            parent[x_root] = y_root
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        parent = [i for i in range(n)]
        
        for u, v in pairs:
            self.union(parent, u, v)
        
        m = collections.defaultdict(list)
        for i in range(n):
            m[self.find_root(parent, i)].append(i)
        
        ans = list(s)
        for _, indices in m.items():
            temp = []
            for i in indices:
                temp.append(s[i])
            temp.sort()
            for i in range(len(temp)):
                ans[indices[i]] = temp[i]
        
        return \"\".join(ans)
    
    def find_root(self, parent, x):
        if parent[x] != x:
            parent[x] = self.find_root(parent, parent[x])
        return parent[x]
    
    def union(self, parent, x, y):
        x_root = self.find_root(parent, x)
        y_root = self.find_root(parent, y)
        if x_root != y_root:
            parent[x_root] = y_root