首页 / 算法 / （算法）并查集及其应用

（算法）并查集及其应用

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了（算法）并查集及其应用，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1342字，纯文字阅读大概需要2分钟。

内容图文

题目：

某国家有N个小岛组成，经过多年的基础设施累积，若该岛屿之间建立若干桥梁，先重新完善该国的行政区划，规定只要有桥梁连接的岛屿则归属于同一个城市（可以通过其他岛屿中转），问该国可以划分为多少个城市？

思路：

并查集

代码：

#include<iostream>
#include<set>
usingnamespace std;

class UnionFindSet{
    private:
        int m_nN;
        int* m_pParent;
    public:
        UnionFindSet(int n);
        ~UnionFindSet();
        void Union(int i,int j);
        int Find(int i);
        void Print() const;
};

UnionFindSet::UnionFindSet(int n){
    m_nN=n;
    m_pParent=newint[m_nN];
    for(int i=0;i<m_nN;i++)
        m_pParent[i]=i;
}

UnionFindSet::~UnionFindSet(){
    if(m_pParent!=NULL){
        delete[] m_pParent;
        m_pParent=NULL;
    }
}

int UnionFindSet::Find(int i){
    if(i<0 || i>=m_nN)
        return -1;
    int root=i;
    while(root!=m_pParent[root])
        root=m_pParent[root];

    int t=i;
    int p;
    while(t!=root){
        p=m_pParent[t];
        m_pParent[t]=root;
        t=p;
    }
    return root;    
}

void UnionFindSet::Union(int i,int j){
    if(i<0 || i>=m_nN || j<0 || j>=m_nN)
        return;
    int ri=Find(i);
    int rj=Find(j);
    if(ri!=rj)
        m_pParent[ri]=rj;
}

int calcComponent(){
    int M,N;
    int c1,c2;
    cin>>M>>N;
    UnionFindSet ufs(N);
    
    for(int i=0;i<M;i++){
        cin>>c1>>c2;
        ufs.Union(c1,c2);
    }

    set<int> numOfComponent;
    for(int i=0;i<N;i++){
        int p=ufs.Find(i);
        numOfComponent.insert(p);
    }

    return numOfComponent.size();
}

int main(){
    cout<< calcComponent()<<endl;

    return0;
}

 

原文：http://www.cnblogs.com/AndyJee/p/4986905.html

内容总结

以上是互联网集市为您收集整理的（算法）并查集及其应用全部内容，希望文章能够帮你解决（算法）并查集及其应用所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1310777.html

来源：【匿名】