本文共 2152 字，大约阅读时间需要 7 分钟。

为了解决这个问题，我们需要找到一种方法，在给定的字符交换对数组的约束下，生成字典序最小的字符串。通过分析，我们可以发现这些交换对实际上定义了连通块，每个连通块中的字符可以任意排列。因此，我们可以将每个连通块内的字符排序，并将它们放置在相应的位置，从而得到最小的字符串。

方法思路

解决代码

class DSU:    def __init__(self, size):        self.parent = list(range(size))        self.rank = [1] * size    def find(self, x):        if self.parent[x] != x:            self.parent[x] = self.find(self.parent[x])        return self.parent[x]    def union(self, x, y):        x_root = self.find(x)        y_root = self.find(y)        if x_root == y_root:            return        if self.rank[x_root] < self.rank[y_root]:            self.parent[x_root] = y_root        else:            self.parent[y_root] = x_root            if self.rank[x_root] == self.rank[y_root]:                self.rank[x_root] += 1def smallestStringWithSwaps(s, pairs):    n = len(s)    if n == 0:        return s    dsu = DSU(n)    for a, b in pairs:        dsu.union(a, b)    from collections import defaultdict    groups = defaultdict(list)    for i in range(n):        root = dsu.find(i)        groups[root].append(i)    for root in groups:        indices = groups[root]        chars = [s[i] for i in indices]        chars_sorted = sorted(chars)        s_list = list(s)        for i in range(len(indices)):            s_list[indices[i]] = chars_sorted[i]        s = ''.join(s_list)    return s# 读取输入import sysdef main():    s = sys.stdin.readline().strip()    if not s:        print("")        return    pairs = []    while True:        line = sys.stdin.readline()        if not line:            break        line = line.strip()        if not line:            continue        a, b = map(int, line.split(','))        pairs.append( (a, b) )    result = smallestStringWithSwaps(s, pairs)    print(result)if __name__ == "__main__":    main()

代码解释

通过这种方法，我们能够在允许的交换操作下，高效地生成字典序最小的字符串。