简介
并查集是一种数据结构，一般它处理的是图(其实是解决无向图的)的连通分量问题，但是当并查集的根节点可以维护更多的信息时，并查集可以解决范围更广的基于无向图连通分量的问题。做了这么多并查集的题目后，我感觉并查集就是解决有关物与物之间的关系问题的数据结构且这种关系还必须是可传递的关系，所以一般遇到这种问题可以先尝试用并查集解决。
并查集操作比较简单，主要是理解路径压缩、按值归并、带权并查集就ok了。
题目
547. 朋友圈(求无向图连通分量)
684. 冗余连接(无向图、连通分量)
685. 冗余连接 II(上一题的改编)
839. 相似字符串组(无向图、连通分量)
面试题 17.07. 婴儿名字(按秩归并)
200. 岛屿数量(解决一种DFS经典水洼问题)
547. 朋友圈(求无向图连通分量)
class Solution {
public://并查集操作int fa[11111];int Find(int x){return fa[x]<0?x:fa[x] = Find(fa[x]);}bool Union(int x,int y){int rx = Find(x), ry = Find(y);if(rx == ry)return false;fa[rx] = ry;return true;}int findCircleNum(vector<vector<int>>& M) {memset(fa,-1,sizeof fa);int n = M.size(); if(!n) return 0;int m = M[0].size();for(int i = 0;i<n;++i)for(int j = 0;j<m;++j){if(M[i][j])Union(i,j);}int ans = 0;for(int i = 0;i<n;++i){if(fa[i]<0)ans++;}return ans;}
};//dfs
class Solution {
public:int findCircleNum(vector<vector<int>>& M) {int n = M.size();if(!n) return 0;int m = M[0].size();vector<bool> vis(n+1,false);int ans = 0;for(int i = 0;i<n;++i){if(!vis[i]){ans++;dfs(M,vis,i);}}return ans;}void dfs(vector<vector<int>>&M,vector<bool>&vis,int i){if(vis[i]) return;vis[i] = true;for(int j = 0;j<M.size();++j){if(i==j)continue;if(M[i][j] == 1 && !vis[j])dfs(M,vis,j);}}
};684. 冗余连接(无向图、连通分量)
class Solution
{public:int fa[11111];int Find(int x){return fa[x]<0?x:fa[x] = Find(fa[x]);}bool Union(int x,int y){int rx = Find(x), ry = Find(y);if(rx == ry)return false;fa[rx] = ry;return true;}vector<int> findRedundantConnection(vector<vector<int>>& edges) {memset(fa,-1,sizeof fa);int n = edges.size();for(int i = 0;i<n;++i){if(!Union(edges[i][0],edges[i][1]))return edges[i];}return std::vector<int>{};}
};685. 冗余连接 II(上一题的改编)
class Solution {
public:int fa[11111];int Find(int x){return fa[x]<0?x:fa[x] = Find(fa[x]);}bool Union(int x,int y){int rx = Find(x), ry = Find(y);if(rx == ry)return false;fa[rx] = ry;return true;}vector<int> check(vector<vector<int>>& edges,int except){memset(fa,-1,sizeof fa);for(int i = 0;i<edges.size();++i){if(i==except)continue;if(!Union(edges[i][0],edges[i][1]))return edges[i];}return {};}vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int n = edges.size(); std::vector<int> degree(n+11,0);for(auto &x:edges) ++degree[x[1]];for(int i = n-1;i>=0;--i){if(degree[edges[i][1]] == 2 && !check(edges,i).size()){//倒叙找出入度为2的点，不带这条边是否符合题意，如果符合，则返回这条边return edges[i];}}return check(edges,n);}
};839. 相似字符串组(无向图、连通分量)
class Solution {
public:bool isSame(string &a,string &b){int n = a.size(),m=b.size();if(n != m) return false;int cnt = 0;for(int i = 0;i<n;++i){if(a[i]!=b[i]){cnt++; }}if(cnt == 0 || cnt == 2)return true;return false;}vector<int>fa;int Find(int x){return x == fa[x]? x: fa[x] = Find(fa[x]);}void Union(int x,int y){int fx=Find(x),fy = Find(y);if(fx == fy)return;fa[fx] = fy;}int numSimilarGroups(vector<string>& A) {int n = A.size();fa.resize(n);for(int i = 0;i<n;++i)fa[i] = i;for(int i = 0;i<n;++i){for(int j = i+1;j<n;++j){if(isSame(A[i],A[j])){Union(i,j);}}}int ans = 0;for(int i = 0;i<n;++i)if(fa[i]==i){ans++;}return ans;}
};面试题 17.07. 婴儿名字(按秩归并)
class Solution {
public:unordered_map<string,string> fa;//并查集关系unordered_map<string,int> mp;//并查集权值:集合大小// unordered_map<string,int> mp;string Find(string x){return fa[x] == x?x:fa[x] = Find(fa[x]);}void Union(string x,string y){string fax = Find(x);string fay = Find(y);if(fax == fay)return;if(fax<fay)fa[fay] = fax,mp[fax] += mp[fay];//按秩归并，往字典序小的上面靠else fa[fax] = fay,mp[fay] += mp[fax];}vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {for(auto x:names){//初始化int pos = x.find("(");string name = x.substr(0,pos);int pos2 = x.find(")");string fre = x.substr(pos+1,pos2-pos+1);mp[name] = stoi(fre);fa[name] = name;}for(auto x:synonyms){//初始化int pos = x.find(",");int pos2 = x.find(")");int sz = x.size();string name1 = x.substr(1,pos-1);string name2 = x.substr(pos+1,sz-1-pos-1);fa[name1] = name1;fa[name2] = name2;}for(auto x:synonyms){//合并int pos = x.find(",");int pos2 = x.find(")");int sz = x.size();string name1 = x.substr(1,pos-1);string name2 = x.substr(pos+1,sz-1-pos-1);// fa[name1] = name1;// fa[name2] = name2;Union(name1,name2);}vector<string>ans;for(auto x:fa){if(x.first == x.second){string s = x.first + "(" + to_string(mp[x.first]) + ")" ;ans.push_back(s);}}return ans;}};
200. 岛屿数量(解决一种DFS经典水洼问题)
class Solution {
public://并查集操作int fa[111111];int Find(int x){return fa[x]<0?x:fa[x] = Find(fa[x]);}bool Union(int x,int y){int rx = Find(x), ry = Find(y);if(rx == ry)return false;fa[rx] = ry;return true;}int d[4][2] = {
{-1,0},{1,0},{0,-1},{0,1}};int numIslands(vector<vector<char>>& grid) {int n = grid.size();if(!n)return 0;int m = grid[0].size();memset(fa,-1,sizeof fa);for(int i = 0;i<n;++i)for(int j = 0;j<m;++j){if(grid[i][j] == '1'){for(int k = 0;k<4;++k){int dx = i+d[k][0];int dy = j+d[k][1];if(dx<0||dx>=n||dy<0||dy>=m)continue;if(grid[dx][dy] == '1')Union(i*m+j,dx*m+dy);}}}int ans = 0;for(int i = 0;i<n;++i)for(int j = 0;j<m;++j){if(grid[i][j]=='1' && fa[i*m+j]==-1)++ans;}return ans;}
};//dfs
class Solution {
public:int numIslands(vector<vector<char>>& M) {int n = M.size();if(!n) return 0;int m = M[0].size();int ans = 0;for(int i = 0;i<n;++i)for(int j = 0;j<m;++j){if(M[i][j] == '1')ans++,dfs(M,i,j,n,m);}return ans;}void dfs(vector<vector<char>>&M,int i,int j,int n,int m){if(i>=n || i<0 || j>=m || j<0)return;if(M[i][j] != '1')return;M[i][j] = '0';dfs(M,i+1,j,n,m);dfs(M,i-1,j,n,m);dfs(M,i,j-1,n,m);dfs(M,i,j+1,n,m);}
};