<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>

class Solution:
    
    def dfs(
        self, 
        string: list[str], 
        index: int, 
        indices: list[int], 
        chars: list[str],
        graph: dict[int, list[int]],
        visited: set[int],
    ):
        indices.append(index)
        chars.append(string[index])

        visited.add(index)

        for neighbor in graph[index]:
            if neighbor in visited:
                continue
            
            self.dfs(string, neighbor, indices, chars, graph, visited)


    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        """
        This can be solved thinking of the INDICES of the string as
        nodes of a graph, and the `pairs` as the edges that connect them.

        If we think of that graph, then we can do a DFS along the graph
        and store both the indices and the chars we find in those indices
        following the thought that:
            - If we can see any of these indices and chars along a DFS,
            then we'll be able to swap successively until we put any
            of those chars in any of those indices.

        Knowing that, we just want to sort the list of indices we saw
        and the chars we saw, ascending, and place the smallest chars
        in the smallest indices.

        We repeat this process for each disconnected component of the
        swapping graph.
        """
        string = list(s)

        graph = defaultdict(list)
        for edge in pairs:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])

        visited = set()
        for index in range(len(s)):
            # We don't want to do this more than once per connected component
            if index in visited:
                continue
            
            chars = []
            indices = []
            self.dfs(string, index, indices, chars, graph, visited)


            # Just place the smallest char possible in the first index possible
            chars.sort()
            indices.sort()
            for swap_index, char in zip(indices, chars):
                string[swap_index] = char
        
        return ''.join(string)
517