并查集

优质参考博客

• 并查集
• 并查集简记

Leetcode 题目

• 1202.交换字符串中的元素

对应题解

• 1202 [from Andy at Leetcode]

  class Solution {
  public:
      int father[100010];
      int find(int x)//并查集find
      {
          return x==father[x]?x:(father[x] = find(father[x]));
      }
      void merge(int x,int y)//并查集merge
      {
          father[find(x)] = find(y);
      }
      string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
          int n = s.size();
          string areastr[100010]; //areastr[x]含义为并查集里所有father==x的结点集合
          int cnt[100010] ={0};//cnt[x]含义为areastr[x]内的第一个未分配元素
          for(int i=0; i<n; i++) father[i] = i;//初始化并查集
          for(auto i: pairs) merge(i[1], i[0]);//merge连通结点
          for(int i=0; i<n; i++)
              areastr[find(i)]+=s[i];//将s[i]添加到连通结点集合内
          for(int i=0; i<n; i++)
              sort(areastr[i].begin(),areastr[i].end());//对每个连通图内容排序
          for(int i=0; i<n; i++)
              s[i] = areastr[father[i]][cnt[find(i)]++];//根据连通图内排序后结果还原字符串
          return s;
      }
  };