<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 smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        """
        If two pairs intersect, then it means that all involved locations can be swapped (bubble swap sort).
        So, ideally, we only need to create major cliques where elements can be sorted, sort them out, and concatenate.
        """
        n = len(s)

        # Create a graph of all locations.
        graph = {idx: set() for idx in range(n)}
        
        # Process each pair for adjacency.
        for pair in pairs:
            u, v = pair
            graph[u].add(v)
            graph[v].add(u)

        # Now, get all cliques from this graph.
        cliques = []
        
        while graph:
            # Select any node from graph.
            key = None
            for key_ in graph:
                key = key_
                break
            
            # Now, starting at this key, run a DFS or BFS, to get all nodes.
            visited = set()
            queue = set([key])

            while queue:
                curr = queue.pop()
                visited.add(curr)

                for neighbor in graph[curr]:
                    if neighbor not in visited:
                        queue.add(neighbor)

            # Delete off visited nodes from graph.
            for node in visited:
                del graph[node]

            # Add this clique.
            cliques.append(tuple(sorted(visited)))

        # print(cliques)

        # For each clique, get the corresponding characters and sort.
        clique_to_sorted_substring = {}
        for clique in cliques:
            clique_to_sorted_substring[clique] = sorted(
                [s[idx] for idx in clique]
            )

        # print(clique_to_sorted_substring)

        ans = [None for idx in range(n)]
        for clique, substring in clique_to_sorted_substring.items():
            for idx, ch in zip(clique, substring):
                ans[idx] = ch

        return "".join(ans)
                
777