Leetcode No.1202 交换字符串中的元素

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        
        # 把 pair索引对看成无向图的路径，那么pairs[i] = [a, b]表示存在路径 <a, b>
        # 使用图的遍历算法，计算出图的所有连通分量，及在同一个连通分量的所有字符
        # 同一个连通分量的字符可以任意交换位置，如[0, 3], [0, 2]，则索引0, 2, 3的字符可以任意相互交换 
        # 对同一个连通分量的字符进行排序，再按相应的索引放回到原字符串中，即可得到按字典序升序的最小字符串
        # 可以使用DFS，或BFS

        # DFS,  conn-同一个连通图的所有字符索引，G-邻接矩阵，- u-当前访问节点, visit-标记节点是否被访问过
        def dfs(conn, u, visit, G):
            for v in G[u]:
                # 节点u的相邻节点v没有访问过
                if visit[v] == False:
                    visit[v] = True
                    conn.append(v)
                    dfs(conn, v, visit, G)

        # BFS
        def bfs(conn, G, visit, u):
            # list模拟队列
            queue = []
            queue.append(u)
            while queue:
                # 取队首结点
                front = queue.pop(0)
                for v in G[front]:
                    # 结点v没有入队
                    if visit[v] == False:
                        visit[v] = True
                        queue.append(v)
                        conn.append(v)
        
        
        n = len(s)
        G = [[] for _ in range(n)]
        # 更加pair建立图的邻接矩阵
        for u, v in pairs:
            G[u].append(v)
            G[v].append(u)
        
        # visit[i]标记节点i是否访问过
        visit = [False] * n
        ans = list(s)
        for u in range(n):
            # 节点u没有访问过，则遍历u所在的连通分量
            if visit[u] == False:
                conn = []
                # DFS
                # dfs(conn, u, visit, G)
                
                # BFS
                bfs(conn, G, visit, u)

                # 对连通分量的节点（字符索引）进行升序
                index = sorted(conn)
                # 对连通分量节点（索引）对应的字符进行升序
                t = sorted(ans[i] for i in conn)
                # 按升序后的位置更新s, index是字符索引，t是字符
                for i, ch in zip(index, t):
                    ans[i] = ch
                    # print("ans[{}] = {}".format(i, ch))

        return "".join(ans)