Leetcode1202. 交换字符串中的元素 (dsu,贪心）

class dsu:
    def __init__(self,n):
        self.n=n
        self.f=list(range(n))
        self.rk=[1]*n
    def find(self,x):
        if self.f[x]!=x:
            self.f[x]=self.find(self.f[x])
        return self.f[x]
    def union(self,x,y):
        fx,fy=self.find(x),self.find(y)
        if fx!=fy:
            if self.rk[fx]<self.rk[fy]:
                fx,fy=fy,fx
            self.f[fy]=fx
            self.rk[fx]+=self.rk[fy]
    

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        dsu1=dsu(len(s))
        for x,y in pairs:
            dsu1.union(x,y)
        mp=collections.defaultdict(list)
        for i,ch in enumerate(s):
            mp[dsu1.find(i)].append(ch)
        for i in mp.values():
            i.sort()
        ans=''
        for i in range(len(s)):
            ans+=mp[dsu1.find(i)][0]
            del mp[dsu1.find(i)][0]
        return ans