PAT1034. Head of a Gang ——离散化+并查集

题意：成员A与成员B通话 ，成员B与成员C通话，则 ABC即为一个团伙，一共有若干个团伙，每个团伙的人数大于2且相互通话时间超过一定值即为黑帮，每个黑帮伙里有一个BOSS，boss是与各个成员打电话最多的那一个，找出所有黑帮boss跟与之相应成员数，按字典序排列。

分析：通话姓名是字符串，不好直接构图，离散化一下，在用并查集确定团伙，在查找黑帮与BOSS

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<stack>

#include<map>

#include<string>

using namespace std;

int bossLen[];

int oneLen[];

int Link[];

int n,K;

map<string,int>mm1; // 字符串对应数字

map<int,string>mm2;//数字对应字符串

int f[];

int point[];

int index=;

struct data{

    string name;

    int linkN;

}node[];

int headNum=;

int find(int n){

    if(f[n]==-)return n;

    return f[n]=find(f[n]);

}

int um(int a,int b){

    int fa=find(a),fb=find(b);

    if(fa==fb)return ;

    else f[fa]=fb;

}

void init(){

    int i;

    for(i=;i<=;i++){

        bossLen[i]=;

        oneLen[i]=;

    }

    for(i=;i<=;i++){

        f[i]=-;

    }

    string str1,str2;

    for(i=;i<=n;i++){

        cin>>str1;

        int ll,rr;

        if(mm1.find(str1)==mm1.end()){

            index++;

            mm1[str1]=index;

            mm2[index]=str1;

            ll=index;

        }else{

            ll=mm1[str1];

        }

        cin>>str2;

        if(mm1.find(str2)==mm1.end()){

            index++;

            mm1[str2]=index;

            mm2[index]=str2;

            rr=index;

        }else{

            rr=mm1[str2];

        }

        int temp;

        scanf("%d",&temp);

        bossLen[ll]+=temp;

        bossLen[rr]+=temp;

        oneLen[ll]+=temp;

        um(ll,rr);

    }

}

int cmp(data x,data y){

    return x.name<y.name;

}

void cal(){

    int i;

    int useground[];

    int hash1[];

    int groundLen[];

    int hashLen[];

    for(i=;i<=index;i++){

        useground[i]=;

        Link[i]=;

        point[i]=find(i);

        hash1[i]=;

        hashLen[i]=;

    }

    for(i=;i<=index;i++){

        hash1[point[i]]++;

    }

    for(i=;i<=index;i++){

        hashLen[point[i]]+=oneLen[i];

        Link[i]=hash1[point[i]];

    }

    for(i=;i<=index;i++){

        groundLen[i]=hashLen[point[i]];

        if(Link[i]>&&groundLen[i]>K){

            if(useground[point[i]]==)continue;//该团伙遍历过，就不要遍历了

            headNum++;

            int rk,max=,k;

            for(k=;k<=index;k++){//找团队中单人最多通话，就是老大

                if(point[i]!=point[k])continue;

                if(bossLen[k]>max){

                    max=bossLen[k];

                    rk=k;

                }

            }

            useground[point[rk]]=;

            node[headNum].linkN=Link[rk];

            node[headNum].name=mm2[rk];

        }

    }

    printf("%d\n",headNum);

    sort(&node[],&node[headNum+],cmp);

    for(i=;i<=headNum;i++){

        cout<<node[i].name<<" "<<node[i].linkN<<endl;

    }

}

int main()

{

    while(scanf("%d%d",&n,&K)!=EOF){

        int i;

        init();

        cal();

    }

    return ;

}