并查集模板

1.合并2个点时，可以判断2个点是否属于一个联通分量，如果不属于，那么加入该连通分量，
2. 最后判断该图 有几个单独的联通分量，
3. 或者将图压缩成 最小生成树时，判断每个点是否属于最小生成树中，不是就加入树中，

  • 用一个pre[i]表示点i在图中的顶点，初始化时每个点i（都是一个单独的联通分量）所以顶点就是，判断联通分量的数量也是判断pre[i] == i，
  • 合并两个u,v，一开始标记pre[u]=v pre[v]=u都行，说明他们是另一个的父亲节点,但是如果一条链上点多了，每个点的只能记录它的父亲节点，就没有达到标记图的顶点的目的,这是要用到一个叫做路径压缩的方法
  • 路径压缩，先找到点i的顶点,然后不断的将该条路上的点的父亲节点都设置成顶点,
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    重要的是路径压缩
    #include<iostream> 
    using namespace std;
    const int maxn=1000+10;
    int pre[maxn];//记录每一个点的前一个节点，（最后都变成该点的根节点）
    int find(int x){//寻找点x的根节点
        int root=x;
        while( pre[root]!=root )//当前点的根节点不是自己
            root=pre[root];//一直向前找
        //路径压缩，所有点的前一个点都为根节点   减少时间复杂度
        while(pre[x]!=root){
            int k=pre[x];//当前点的前一个点暂时保存
            pre[x]=root;//当前点的前一个点为根节点
            x=k;//继续遍历当前点的前一个点
        }
        return root;
    }
    void merge(int a,int b){//将两点代表的连通分量连成一个连通分量
        if( find(a)!=find(b) ) //属于相同连通分量就不连，
            pre[find(a)]=find(b);//a的根节点的父亲可以使b根节点父亲，反之成立
    }
    int main(){
        int n,m;// n个节点，m条边。
        cin>>n>>m;
        for(int i=1;i<=n;i++)   pre[i]=i;
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            merge(a,b);
        }
        //看有几个连通分量
        int ans=0;
        for(int i=1;i<=n;i++)//根节点代表自己就是一个独立的连通分量
            if( pre[i]==i )  ans++;
        cout<<ans;
        return 0;
    }