PAT1034 Head of a Gang 并查集实现

左手的ㄟ右手 2023-02-21 12:48 17阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70][]

利用并查集来实现，一个重要的思想是，对于一个集合而言，将该集合所有有关的信息捆绑到根节点上，当数据发生变化时，我们只需要修改该集合下根指向的数据即可

姓名和编号的转换我利用的是map<string,int> ,相应的编号转到姓名为map<int,string>

题中还有一个关于回路问题，转换到并查集中就是当前处理的两个结点在同一集合中，这时更新当前集合的总通话时间和首领信息和两个集合合并情况并不一样，注意区分，详细解析见代码

#include<iostream>
    #include<vector>
    #include<map>
    #include<algorithm>
    using namespace std;
    map<string,int> nametoid;
    map<int,string> idtoname;
    int data[2010];//每个结点的权值
    int head[2010]={0};//每个帮派的首领
    int father[2010]; 
    int isroot[2010]={0};//每个帮派的总通话时间
    int value[2010]={0};//每个帮派的总人数
    int n,k;
    int findroot(int a)//找根结点
    {
        int x=a;
        while(father[a]!=a)
        {
            a=father[a];
        }
        //路径压缩
        while(x!=father[x])
        {
            int c=x;
            x=father[x];
            father[c]=a;
        }
        return a;//返回根结点
    }
    void combine(int a,int b,int c)
    {
        int roa=findroot(a),rob=findroot(b);
        if(roa!=rob)//不属于同一个集合
        {
            isroot[roa]+=isroot[rob];
            isroot[roa]+=c;
            value[roa]+=value[rob];
            if(data[head[rob]]>data[head[roa]])head[roa]=head[rob];
            father[rob]=roa;
            //不同集合，首领应比较a、b、roa,rob，四者中权值最大为首领
            if(data[a]>data[head[roa]])head[roa]=a;
            if(data[b]>data[head[roa]])head[roa]=b;
        }
        else//在同一集合 
        {
        	isroot[roa]+=c;//更新帮派通话总时间
            //同一集合，首领应比较a、b、roa，三者中权值最大为首领
            if(data[a]>data[head[roa]])head[roa]=a;
            if(data[b]>data[head[roa]])head[roa]=b;
    	}
    }
    bool cmp(int a,int b)
    {
        return idtoname[a]<idtoname[b];
    }
    int main()
    {
        cin>>n>>k;
        int cnt=1;//总人数为cnt-1
        for(int i=0;i<2010;i++)
        {
            father[i]=i;
            data[i]=0;
            value[i]=1; 
        }
        for(int i=0;i<n;i++)
        {
            string a,b;
            int c;
            cin>>a>>b>>c;
            //记录姓名
            if(nametoid[a]==0)
            {
                  nametoid[a]=cnt;
                  idtoname[cnt++]=a;
            }
            if(nametoid[b]==0)
            {
                nametoid[b]=cnt;
                idtoname[cnt++]=b;
            }
            //更新点的权值
            data[nametoid[a]]+=c;
            data[nametoid[b]]+=c;
            combine(nametoid[a],nametoid[b],c);//合并两个点
        }
        //找根节点
        vector<int> v;//存放每个根节点id
        for(int i=1;i<cnt;i++)
    	if(father[i]==i&&isroot[i]>k&&value[i]>2)
        {
            v.push_back(i);
        }
        cout<<v.size()<<endl;
        sort(v.begin(),v.end(),cmp);
        for(int i=0;i<v.size();i++)
        {
            cout<<idtoname[head[v[i]]]<<" "<<value[v[i]]<<endl;
            
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630203111221.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70