Union Find
可以使用「并查集」解决的问题，一般都可以使用「深度优先搜索」和「广度优先搜索」完成。但是「深度优先搜索」和「广度优先搜索」不仅回答了连接问题，还回答了路径问题，时间复杂度高。
重点：
路径压缩
每个操作的复杂度是O（1）
class DisjointSet{
private:
vector<int> fa;
int _find(int x){
if(fa[x]==x)return x;
else{
int t = fa[x];
fa[x] = _find(t);
return fa[x];
}
};
public:
DisjointSet(int size){
for(int i=0;i<size;i++)fa.push_back(i);
};
int _union(int a, int b){
int fa_a = _find(a);
int fa_b = _find(b);
fa[fa_a] = fa_b;
return fa_b;
};
bool same(int a,int b){
return _find(a) == _find(b);
};
bool root(int a){
return fa[a] == a;
}
};399. 除法求值
在并查集的基础上，设计辅助的数组记录信息，灵活运用路经压缩。
class Dict{
private:
map<string, int> str2int;
vector<string> int2str;
public:
Dict(){}
int push(string t){
if(!exists(t)){
str2int.insert(pair<string,int>(t, int2str.size()));
int2str.push_back(t);
}
return str2int[t];
}
bool exists(string t){
return str2int.count(t) != 0;
}
int const operator[](string t){
if(exists(t))
return str2int[t];
else
return -1;
}
string const operator[](int t){
return int2str[t];
}
int size(){
return int2str.size();
}
};
class DisjointSet{
public:
vector<int> fa;
vector<double> rate;
pair<int,double> _find(int x){
if(fa[x]==x)return pair<int,double>(x,1.0);
else{
int t = fa[x];
double r = rate[x];
pair<int,double> tmp = _find(t);
fa[x] = tmp.first;
rate[x] = r*tmp.second;
return pair<int,double>(fa[x],rate[x]);
}
};
DisjointSet(int size){
for(int i=0;i<size;i++){
fa.push_back(i);
rate.push_back(1.0);
}
};
int _union(int a, int b, double r){
pair<int,double> fa_a = _find(a);
pair<int,double> fa_b = _find(b);
fa[fa_a.first] = fa_b.first;
rate[fa_a.first] = r * fa_b.second / fa_a.second;
return fa_b.first;
};
bool same(int a,int b){
return _find(a).first == _find(b).first;
};
bool root(int a){
return fa[a] == a;
}
};
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
vector<double> ans;
Dict dict;
DisjointSet ds(500);
for(int i=0;i<equations.size();i++){
string a = equations[i][0];
string b = equations[i][1];
double v = values[i];
int ia = dict.push(a);
int ib = dict.push(b);
ds._union(ia, ib, v);
}
// for(int i=0;i<dict.size();i++){
// cout << "#" << i << endl;
// cout << dict[i] << endl;
// cout << ds.fa[i] << endl;
// cout << ds.rate[i] << endl;
// }
for(int i=0;i<queries.size();i++){
int ia = dict[queries[i][0]];
int ib = dict[queries[i][1]];
double t_ans;
if(ia == -1 || ib == -1){
t_ans = -1.0;
}else{
if(ds.same(ia,ib)){
double r1 = ds._find(ia).second;
double r2 = ds._find(ib).second;
t_ans = r1/r2;
}else{
t_ans = -1.0;
}
}
// cout << "ans:" << t_ans << endl;
ans.push_back(t_ans);
}
return ans;
}
};959. 由斜杠划分区域
这个题目比较一般，没啥特殊的，将每个块分为四个，然后合并对应的块，最后看并查集的个数。
class DisjointSet{
private:
vector<int> fa;
int _find(int x){
if(fa[x]==x)return x;
else{
int t = fa[x];
fa[x] = _find(t);
return fa[x];
}
};
public:
DisjointSet(int size){
for(int i=0;i<size;i++)fa.push_back(i);
};
int _union(int a, int b){
int fa_a = _find(a);
int fa_b = _find(b);
fa[fa_a] = fa_b;
return fa_b;
};
bool same(int a,int b){
return _find(a) == _find(b);
};
bool root(int a){
return fa[a] == a;
}
int blocks(){
int cnt = 0;
for(int i=0;i<fa.size();i++){
if(root(i))cnt++;
}
return cnt;
}
};
class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
DisjointSet ds(grid.size()*grid.size()*4);
for(int i=0;i<grid.size();i++){
int cnt_i = grid.size()*4*i;
for(int j=0;j<grid[i].size();j++){
if(j!=grid[i].size()-1){
ds._union(cnt_i+j*4+2,cnt_i+(j+1)*4+0);
}
if(grid[i][j]=='\\'){
ds._union(cnt_i+j*4+1,cnt_i+j*4+2);
ds._union(cnt_i+j*4+0,cnt_i+j*4+3);
}else if(grid[i][j]=='/'){
ds._union(cnt_i+j*4+0,cnt_i+j*4+1);
ds._union(cnt_i+j*4+2,cnt_i+j*4+3);
}else{
ds._union(cnt_i+j*4+0,cnt_i+j*4+1);
ds._union(cnt_i+j*4+1,cnt_i+j*4+2);
ds._union(cnt_i+j*4+2,cnt_i+j*4+3);
}
if(i!=grid.size()-1){
ds._union(cnt_i+j*4+3,cnt_i+grid.size()*4+j*4+1);
}
}
}
return ds.blocks();
}
};778. 水位上升的泳池中游泳
这个题目有三种解法
结合二分查找做BFS或DFS遍历 $n^2*logn$
选择不同的高度，然后做遍历，看首尾是否可相连。
并查集
从小到大将点和他的上下左右合并操作，判断起点和终点是否在并查集中。
图的最短路径算法
动态维护从起点到各个定点的最短路径，加上
class DisjointSet{
private:
vector<int> fa;
int _find(int x){
if(fa[x]==x)return x;
else{
int t = fa[x];
fa[x] = _find(t);
return fa[x];
}
};
public:
DisjointSet(int size){
for(int i=0;i<size;i++)fa.push_back(i);
};
int _union(int a, int b){
int fa_a = _find(a);
int fa_b = _find(b);
fa[fa_a] = fa_b;
return fa_b;
};
bool same(int a,int b){
return _find(a) == _find(b);
};
bool root(int a){
return fa[a] == a;
}
};
class Solution {
public:
int dires[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
bool vaild(int x,int y,int N){
return (x>=0)&&(y>=0)&&(x<N)&&(y<N);
}
void deal(int i,vector<vector<int>>& grid,DisjointSet& ds){
int N = grid.size();
int x=i/N;
int y=i%N;
for(int j=0;j<4;j++){
int nx = x + dires[j][0];
int ny = y + dires[j][1];
if(vaild(nx,ny,N)){
if(grid[nx][ny]<=grid[x][y]){
ds._union(i,nx*N+ny);
}
}
}
}
int swimInWater(vector<vector<int>>& grid) {
int N = grid.size();
DisjointSet ds(N*N);
map<int, vector<int> > m;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
int r = i*N+j;
int v = grid[i][j];
if(m.count(v)==0){
m.insert(pair<int,vector<int> >(v,vector<int>()));
}
m[v].push_back(r);
}
}
for(auto iter=m.begin();iter!=m.end();iter++){
for(int j=0;j<iter->second.size();j++){
deal(iter->second[j],grid,ds);
}
if(ds.same(0,N*N-1)){
return iter->first;
}
}
return 0;
}
};图算法
#define inf 0x7fffffff
class node{
public:
int x;
int y;
int v;
node(int x,int y,int v):x(x),y(y),v(v){}
bool operator<(const node& b) const {
return v > b.v;
}
};
class Solution {
public:
int dires[4][2] = {{0,-1},{0,1},{1,0},{-1,0}};
bool vaild(int x,int y,int N){
return (x>=0)&&(y>=0)&&(x<N)&&(y<N);
}
int swimInWater(vector<vector<int>>& grid) {
int N = grid.size();
vector<vector<bool>> vis(N,vector<bool>(N,false));
priority_queue<node> dist;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i==0&&j==0)dist.push(node(i,j,grid[i][j]));
else dist.push(node(i,j,inf));
}
}
while(true){
auto t = dist.top();
dist.pop();
if(t.x == N-1 && t.y == N-1){
return t.v;
}
vis[t.x][t.y]=true;
for(int i=0;i<4;i++){
int nx = t.x + dires[i][0];
int ny = t.y + dires[i][1];
if(vaild(nx,ny,N)&&!vis[nx][ny]){
dist.push(node(nx,ny,max(t.v,grid[nx][ny])));
}
}
}
return 0;
}
};1202. 交换字符串中的元素
可以推导出：交换关系可以传递
需要注意：
需要建立并查表的倒排，否则会超时间
class DisjointSet{
private:
vector<int> fa;
public:
int _find(int x){
if(fa[x]==x)return x;
else{
int t = fa[x];
fa[x] = _find(t);
return fa[x];
}
};
DisjointSet(int size){
for(int i=0;i<size;i++)fa.push_back(i);
};
int _union(int a, int b){
int fa_a = _find(a);
int fa_b = _find(b);
fa[fa_a] = fa_b;
return fa_b;
};
bool same(int a,int b){
return _find(a) == _find(b);
};
bool root(int a){
return fa[a] == a;
}
};
class Solution {
public:
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
DisjointSet ds(s.length());
for(int i=0;i<pairs.size();i++){
ds._union(pairs[i][0],pairs[i][1]);
}
map<int, vector<int> > m;
for(int i=0;i<s.length();i++){
int r = ds._find(i);
if(m.count(r)==0){
m.insert(pair<int,vector<int> >(r,vector<int>()));
}
m[r].push_back(i);
}
for(auto iter=m.begin();iter!=m.end();iter++){
vector<int> nums(27,0);
int root = iter->first;
vector<int> rs = iter->second;
for(int j=0;j<rs.size();j++){
nums[s[rs[j]]-'a']++;
}
int t=0;
for(int j=0;j<rs.size();j++){
while(nums[t]==0)t++;
s[rs[j]] = 'a'+t;
nums[t]--;
}
}
return s;
}
};947. 移除最多的同行或同列石头
首先需要明确的是：同行同列的都属于一个并查集，然后按照规则每个并查集只会留下一颗石头。
class DisjointSet{
private:
vector<int> fa;
int _find(int x){
if(fa[x]==x)return x;
else{
int t = fa[x];
fa[x] = _find(t);
return fa[x];
}
};
public:
DisjointSet(int size){
for(int i=0;i<size;i++)fa.push_back(i);
};
int _union(int a, int b){
int fa_a = _find(a);
int fa_b = _find(b);
fa[fa_a] = fa_b;
return fa_b;
};
bool same(int a,int b){
return _find(a) == _find(b);
};
bool root(int a){
return fa[a] == a;
}
int count(){
int cnt=0;
for(int i=0;i<fa.size();i++)
if(root(i))cnt++;
return cnt;
}
};
class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
int cnt = 0;
DisjointSet ds(stones.size());
map<int,vector<int>> m0,m1;
map<pair<int,int>, int> pos2rank;
for(int i=0;i<stones.size();i++){
pos2rank.insert(pair<pair<int,int>, int>(pair<int,int>(stones[i][0],stones[i][1]),i));
if(m0.count(stones[i][0])==0){
m0.insert(pair<int,vector<int>>(stones[i][0],vector<int>()));
}
m0[stones[i][0]].push_back(stones[i][1]);
if(m1.count(stones[i][1])==0){
m1.insert(pair<int,vector<int>>(stones[i][1],vector<int>()));
}
m1[stones[i][1]].push_back(stones[i][0]);
}
for(auto iter=m0.begin();iter!=m0.end();iter++){
int x = iter->first;
vector<int>& ys = iter->second;
for(int j=0;j<ys.size()-1;j++){
ds._union(pos2rank[pair<int,int>(x,ys[j])],pos2rank[pair<int,int>(x,ys[j+1])]);
}
}
for(auto iter=m1.begin();iter!=m1.end();iter++){
int y = iter->first;
vector<int>& xs = iter->second;
for(int j=0;j<xs.size()-1;j++){
ds._union(pos2rank[pair<int,int>(xs[j],y)],pos2rank[pair<int,int>(xs[j+1],y)]);
}
}
return stones.size()-ds.count();
}
};803. 打砖块
Last updated
Was this helpful?