程序猴算法日记

一、并查集
- 知识点
- 1.合并集合
- 2.连通块中点的数量
- 3.食物链
- 4.被围绕的区域
- 5.最长连续序列
- 6.岛屿数量
- 7.除法求值
- 8.账户合并
- 9.冗余连接
- 10.省份数量

一、并查集知识点

并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。
重点，短命短思维巧

快速支持俩操作
树形式维护集合
根节点编号就是集合编号
每个点存父节点

并查集维护额外信息
并查集本质记住find函数，其他靠推导
按秩合并，用的少，小树接大树

1.合并集合

#include
using namespace std;

int p[100010];

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    // 如果当前结点不是该集合祖宗结点就递归找。
    //因为要优化路径压缩，找出来顺便都赋值给所有结点的父节点。时间复杂度降到O(1)
    return p[x];
    // 返回老爸一层层递归往上找嘛
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--){
        char ops[2];
        cin>>ops;
        // 行末空格回车自动清，所以是数组
        int a,b;
        cin>>a>>b;
        if(ops[0]=='M'){
            if(find(a)!=find(b)){//find是看祖宗是不是一样，顺便路径压缩了
                p[p[a]]=p[b];
                // 如果祖宗结点不一样，直接把自己祖宗认另一个祖宗当爹，
                //这样就合并了，大家祖宗都一样了
            }
        }else if(ops[0]=='Q'){
            if(find(a)==find(b)) cout<<"Yes";
            else cout<<"No";
            puts("");
        }
    }
}

2.连通块中点的数量

#include
using namespace std;

const int N=100010;

int p[N],size1[N];

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    // 如果当前结点不是该集合祖宗结点就递归找。
    //因为要优化路径压缩，找出来顺便都赋值给所有结点的父节点。时间复杂度降到O(1)
    return p[x];
    // 返回老爸一层层递归往上找嘛
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
       p[i]=i;
       size1[i]=1;//刚开始自己是一个集合
    }
    while(m--){
        char ops[2];
        cin>>ops;
        // 行末空格回车自动清，所以是数组
        int a,b;
        if(ops[0]=='C'){
            cin>>a>>b;
            if(find(a)!=find(b)){//find是看祖宗是不是一样，顺便路径压缩了
                size1[p[b]]+=size1[p[a]];//先算结点数哈，不然都连一起了算个锤子啊，下面那个操作侵入
                p[p[a]]=p[b];
                // 如果祖宗结点不一样，直接把自己祖宗认另一个祖宗当爹，
                //这样就合并了，大家祖宗都一样了
            }
        }else if(ops[1]=='1'){
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes";
            else cout<<"No";
            puts("");
        }else{
            cin>>a;
            cout< 
3.食物链 

 
 
 并查集维护额外信息
 
 
 
  
#include
using namespace std;

int p[50010];
int dis[50010];

int find(int x){
    if(p[x]!=x){
        int t=find(p[x]);//要先求出并保存祖先结点，因为下面算距离要用
        dis[x]+=dis[p[x]];
        p[x]=t;//算完才能给父节点赋值，不然找不到父节点了
    }
    return p[x];
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    int res=0;
    while(m--){
        int ops;
        cin>>ops;
        int x,y;
        cin>>x>>y;
        if(x>n||y>n){
            res++;
            continue;
        }
        int px=find(x),py=find(y);
        if(ops==1){
            if(px==py&&(dis[y]-dis[x])%3){//在同一个集合就判断是不是模三意义下的同级关系，不是就res加
                res++;
            }else if(px!=py){//不在一个集合那就合并嘛
                p[px]=py;
                dis[px]=dis[y]-dis[x];
            }
        }else{
            if(px==py&&(dis[y]-dis[x]+1)%3){//在同一个集合就判断是不是模三意义下的吃的关系，不是就res加
                res++;
            }else if(px!=py){
                p[px]=py;
                dis[px]=dis[y]+1-dis[x];
            }
        }
    }
    cout< 
4.被围绕的区域 

  
class Solution {
public:
    static const int N=40010;

    int p[N]={0};
    int dx[4]={0,-1,0,1};
    int dy[4]={1,0,-1,0};
    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }

    void solve(vector>& board) {
        int L=board.size();
        int C=board[0].size();
        for(int i=0;i<=L*C;i++){//这里要L*C是为了多出一个虚拟节点方便当
        //做所有保留的O结点的父节点，标记用的
            p[i]=i;
        }
        for(int i=0;i=0&&j+dy[k]>=0&&i+dx[k] 
5.最长连续序列 
 
class Solution {
public:
    maphash;//用于查看是否有过某个数字
    static const int N=100010;
    int p[N]={0};
    int size1[N];//以某个下标的数在内的并且最大下标不超过这个数下标的最长连续序列长度
    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
    int longestConsecutive(vector& nums) {
        int L=nums.size();
        if(L==0) return 0;
        if(L==1) return 1;
        int res=1;
        for(int i=0;i 
6.岛屿数量 

  
class Solution {
public:
    static const int L=90010;

    int p[L];

    int dx[2]={1,0};
    int dy[2]={0,-1};//只能俩方向，因为四个方向会重复算噢~

    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }

    int numIslands(vector>& grid) {
        int res=0;
        int M=grid.size(),N=grid[0].size();
        for(int i=0;i=0&&i+dx[k]=0&&j+dy[k] 
7.除法求值 

 
 
 我麻了这题，写了几个小时你们猜吧，还是看答案之后搞的。。。
 既然问题转变为图又与连接关系有关，那么很自然的想到并查集（并查集可以判断两点之间是否连通）。 
class Solution {
public:

    const static int L=210;

    vector val=vector(L,1.0);//并查集树中额外信息的存处，默认是1，自己跟祖先的比值

    int p[L];

    int idx=0;//配映射，因为下面值是字符
    maphash;

    int find(int x){
        if(p[x]!=x){
            int t=p[x];//先拿父节点出来，待会要用，不然等一下路径压缩直接没了
            p[x]=find(p[x]);
            val[x]*=val[t];//自己到祖先的值等于自己到现在祖先的值乘现在祖先到后面祖先的值
        }
        return p[x];
    }

    vector calcEquation(vector>& equations, vector& values, vector>& queries) {
        int N=equations.size();
        for(int i=0;i res;
        for(auto i:queries){
            if(hash.find(i[0])==hash.end()||hash.find(i[1])==hash.end()){//并查集中没存过
                res.push_back(-1.0);
            }else if(find(hash[i[0]])==find(hash[i[1]])){//集合相同
                res.push_back(val[hash[i[0]]]/val[hash[i[1]]]);
            }else{//集合不同
                res.push_back(-1.0);
            }
        }
        return res;
    }
};
 
 
8.账户合并 

  
class Solution {
public:

    static const int L=10010;

    vectorp=vector(L,1);

    unordered_map mp;//账户和它对应的idx

    unordered_map> ms;//存某idx或者说是根和它下面的账户，自动去重排序

    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }

    vector> accountsMerge(vector>& accounts) {
        vector> res=vector>();
        int N=accounts.size();
        for(int i=0;i resSon;
            resSon.push_back(accounts[i.first][0]);//先装名字
            for(auto j:ms[i.first]){
                resSon.push_back(j);
            }
            res.push_back(resSon);
        }
        return res;
    }
};
 
9.冗余连接 

  
class Solution {
public:

    const static int L=2001;

    vector p=vector(L,1);

    int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }

    vector findRedundantConnection(vector>& edges) {
        int N=edges.size();
        for(int i=0;i<=N;i++){
            p[i]=i;
        }
        vectorres;
        for(int i=0;i 
10.省份数量 

  
class Solution {
public:

    static const int L=40010;

    vectorp=vector(L,1);

    int find(int x){
        if(p[x]!=x){
            p[x]=find(p[x]);
        }
        return p[x];
    }

    int findCircleNum(vector>& isConnected) {
        int N=isConnected.size();
        int res=N;//---

        for(int i=0;i

程序猴算法日记

C/C++/C#相关栏目本月热门文章