<p>You are given a string <code>s</code>, and an array of pairs of indices in the string&nbsp;<code>pairs</code>&nbsp;where&nbsp;<code>pairs[i] =&nbsp;[a, b]</code>&nbsp;indicates 2 indices(0-indexed) of the string.</p>

<p>You can&nbsp;swap the characters at any pair of indices in the given&nbsp;<code>pairs</code>&nbsp;<strong>any number of times</strong>.</p>

<p>Return the&nbsp;lexicographically smallest string that <code>s</code>&nbsp;can be changed to after using the swaps.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;dcab&quot;, pairs = [[0,3],[1,2]]
<strong>Output:</strong> &quot;bacd&quot;
<strong>Explaination:</strong> 
Swap s[0] and s[3], s = &quot;bcad&quot;
Swap s[1] and s[2], s = &quot;bacd&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;dcab&quot;, pairs = [[0,3],[1,2],[0,2]]
<strong>Output:</strong> &quot;abcd&quot;
<strong>Explaination: </strong>
Swap s[0] and s[3], s = &quot;bcad&quot;
Swap s[0] and s[2], s = &quot;acbd&quot;
Swap s[1] and s[2], s = &quot;abcd&quot;</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cba&quot;, pairs = [[0,1],[1,2]]
<strong>Output:</strong> &quot;abc&quot;
<strong>Explaination: </strong>
Swap s[0] and s[1], s = &quot;bca&quot;
Swap s[1] and s[2], s = &quot;bac&quot;
Swap s[0] and s[1], s = &quot;abc&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10^5</code></li>
	<li><code>0 &lt;= pairs.length &lt;= 10^5</code></li>
	<li><code>0 &lt;= pairs[i][0], pairs[i][1] &lt;&nbsp;s.length</code></li>
	<li><code>s</code>&nbsp;only contains lower case English letters.</li>
</ul>

'''
Why is this a graph problem?
If we look at the pairs, there are some overlaps. For example [0, 3], [0, 2], [1, 2]
So that means that if certain indices are connected it doesn't matter if we swap the exact pairs
When certain pairs are transitive we can just sort them lexicographically 
So this is a graph problem where every index is a node and there are certain connected components
We just have to sort these connected components 
We can use DFS or Union-Find for this
'''
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        adj = defaultdict(list)
        for p1, p2 in pairs:
            adj[p1].append(p2)
            adj[p2].append(p1)
        
        # Chars store the chars in a connected component
        # Indices store the index in a connected components
        # We sort chars and indices and then for the smallest index in the component we place the smallest char
        def dfs(index, chars, indices):
            chars.append(s[index])
            indices.append(index)
            seen.add(index)
            for neighbor in adj[index]:
                if neighbor not in seen:
                    dfs(neighbor, chars, indices)
        
        seen = set()
        ans = ["" for _ in range(len(s))]
        for i in range(len(s)):
            if i not in seen:
                chars, indices = [], []
                dfs(i, chars, indices)
                chars.sort()
                indices.sort()
                for j in range(len(chars)):
                    ans[indices[j]] = chars[j]
        return "".join(ans)
58860