Head of a Gang

我使用的并查集
name1,name2,time;
思路：用并查集将name1,name2合并，同时每个连通子图的根，负责记录本连通子图的总权重、总成员数量-----(于是我修改了Union函数)，这里分为2种情况：
（1）name1,name2所在的连通子图不是同一个（即需要合并）
合并之后的本连通子图的总权重=name1所在连通子图根节点的总权重+name2所在连通子图根节点的总权重+两个子图之间的权值
*（2）name1,name2所在的连通子图是同一个（即不需要合并，也就是存在A给B通信，B又给A 通信的这种双向通信情况） *
本连通子图的总权重=本连通子图的总权重+新增权值

个人权重：
例如 x,y,w1; y,z,w2;这两条记录 那么weight_of_each_one[y]=w1+w2;

每次找到团伙之后遍历所有人，找属于该团伙的成员，并寻找头目（即个人权重最大的）
代码tips:

• 整个代码处理过程中全部用的int类型 只在输入和输出的部分做了int与string的转换
• map可以保证最后的结果按字典顺序输出

#include<iostream>
#include<cstdio>
#include<string>
#include<map>

using namespace std;

const int MAX=26;
int father[MAX];
int height[MAX];
int number_of_each_gang[MAX];
int weight_of_each_gang[MAX];
int weight_of_each_one[MAX];
bool visited[MAX];

int ToDigit(string str) {
    return str[0]-'A';
}
string ToString(int x) {
    string ans="";
    //for(int i=0; i<3; i++) {
        ans+=x+'A';
//    }
    return ans;
}
void Init() {
    for(int i=0; i<MAX; i++) {
        father[i]=i;
        height[i]=0;
        number_of_each_gang[i]=1;//刚开始是自己一个人 
        weight_of_each_gang[i]=0;
        visited[i]=false;
        weight_of_each_one[i]=0;
    }
}
int Find(int x) {
    if(x!=father[x]) {
        father[x]=Find(father[x]);
    }
    return father[x];
}
void Union(int x,int y,int weight) {
    x=Find(x);
    y=Find(y);
    if(x!=y) { //不属于同一连通子图
        if(height[x]<height[y]) {//y是根
            father[x]=y;
            weight_of_each_gang[y]+=weight+weight_of_each_gang[x];//两个子图合并加上中间的连接权值 
            number_of_each_gang[y]+=number_of_each_gang[x];//两个子图人员合并
        } else if(height[x]>height[y]) { //x是根
            father[y]=x;
            weight_of_each_gang[x]+=weight+weight_of_each_gang[y];
            number_of_each_gang[x]+=number_of_each_gang[y];
        } else { //x是根
            father[y]=x;
            height[x]++;
            weight_of_each_gang[x]+=weight+weight_of_each_gang[y];
            number_of_each_gang[x]+=number_of_each_gang[y];
        }
    } else { //已经属于同一连通子图 （权值增加  人数不增加）
        weight_of_each_gang[x]+=weight;
    }
}

int main() {

    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF) {
        Init();
        while(n--) {
            string Name1, Name2;
            int Time;
            cin>>Name1>>Name2>>Time;

            int N1=ToDigit(Name1);
            int N2=ToDigit(Name2);
            visited[N1]=true;
            visited[N2]=true;
            weight_of_each_one[N1]+=Time;//个人权值
            weight_of_each_one[N2]+=Time;
            Union(N1,N2,Time);
        }
        int number_of_gang=0;
        map<int,int> head;
        for(int i=0; i<MAX; i++) {
            if(!visited[i]) {
                continue;
            }            
            if(father[i]==i&&number_of_each_gang[i]>2&&weight_of_each_gang[i]>k) { //符合gangs定义
                    number_of_gang++;
                int ID=i;//记录头目的编号(初始化为这个团伙的根成员的编号)
                int max_weight=weight_of_each_one[i];//记录头目的权值(初始化为这个团伙的根成员的权值)
                for(int j=0; j<MAX; j++) {
                    if(!visited[i]||i==j) {
                        continue;
                    }
                    if(Find(j)==i) { //找到属于这个gang的成员
                        if(max_weight<weight_of_each_one[j]) {
                            ID=j;
                            max_weight=weight_of_each_one[j];
                        }
                    }
                }
                head[ID]=number_of_each_gang[i];
            }
        }

        cout<<number_of_gang<<endl;
        if(number_of_gang!=0) {
            map<int,int>::iterator it;
            for(it=head.begin(); it!=head.end(); it++) {
                cout<<ToString(it->first)<<" "<<it->second<<endl;
            }
        }
    }
    return 0;
}