Problem Statement:

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.

Solution:

Create graph using pairs as adjancency list.
Start with a node. Do DFS traversal. Sort the node ids (string indices) and characters both. Then put the characters in order.
Repeat for all nodes. Do not do for already visited nodes.

 
class Solution {
public:
    int n;
    vector<vector<int>> edges;
    vector<bool> visited;
    
    void DFS(int src, vector<int>&visited_nodes)
    {
        visited[src]=true;
        visited_nodes.push_back(src);
        for (int dest: edges[src])
            if (!visited[dest]) DFS(dest, visited_nodes);
    }
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) 
    {
        n = s.size();
        edges =  vector<vector<int>>(n, vector<int>{});
        for (auto p: pairs)
        {
            int u=p[0], v=p[1];
            edges[u].push_back(v);
            edges[v].push_back(u);
        }
        visited = vector<bool>(n, false);
        for (int u=0; u<n; u++)
        {
            if (!visited[u])
            {
                vector<int> visited_nodes;
                DFS(u, visited_nodes);
                vector<char> visited_chars;
                for (int i: visited_nodes) visited_chars.push_back(s[i]);
                sort(visited_chars.begin(), visited_chars.end());
                sort(visited_nodes.begin(), visited_nodes.end());
                for (int i=0; i<visited_nodes.size(); i++)
                    s[visited_nodes[i]]=visited_chars[i];
            }
        }
        return s;
    }
};