Head of a Gang

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 26;
// 成员
typedef struct Person
{
    char name[5]; //名字
    int weight;   //权重
    int parent;   //parent保存集合的根节点下标，根节点的parent保存集合成员个数
    Person()
    {
        parent = -1;
        weight = 0;
    }
} Person;
// 帮派
typedef struct gang
{
    char head[5]; //头目
    int number;   //成员数量
} gang;

Person p[N];
int sum[N]; //保存每个集合的总权重

//字典排序函数
bool cmp(gang a, gang b)
{
    return strcmp(a.head, b.head) < 0;
}
//并查集函数
int FindRoot(int x)
{
    int a = x;
    while (p[x].parent >= 0)
    {
        x = p[x].parent;
    }
    while (p[a].parent >= 0)
    {
        int z = a;
        a = p[a].parent;
        p[z].parent = x;
    }
    return x;
}
void Union(int no1, int no2, int weight)
{
    int p1 = FindRoot(no1), p2 = FindRoot(no2);
    //如果是同一个集合也要加上权重
    if (p1 == p2)
    {
        sum[p1] += weight;
        return;
    } 
    if (p[p1].parent > p[p2].parent)
    {
        p[p2].parent += p[p1].parent;
        p[p1].parent = p2;
        sum[p2] = sum[p1] + sum[p2] + weight;
    }else{
         //根结点p1的parent保存集合成员个数
        p[p1].parent += p[p2].parent;
        //p2的parent保存集合的根节点下标
        p[p2].parent = p1;
        //合并的过程，顺便加上集合的总权重
        sum[p1] = sum[p1] + sum[p2] + weight;
    }
}
int main()
{
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF)
    {
        getchar(); //用于消除缓冲区回车防止字符串输入出错
        int i;
        memset(sum, 0, sizeof(sum));
        while (n--)
        {
            char name1[5], name2[5];
            int weight, no1, no2;
            scanf("%s%s%d", name1, name2, &weight);
            getchar();                                  //用于消除缓冲区同上
            no1 = name1[0] - 'A', no2 = name2[0] - 'A'; //由名字找到这个人下标
            //保存该人的名字,每遇到这个人就要加上一次权重
            strcpy(p[no1].name, name1), p[no1].weight += weight;
            strcpy(p[no2].name, name2), p[no2].weight += weight;
            //合并有联系的人
            Union(no1, no2, weight);
        }
        int ans = 0; //保存帮派数目
        gang g[10];  //结果数组，26个人帮派最多有8个，10的数组够了
        for (i = 0; i < N; i++)
        {
            if (p[i].parent < -2 && sum[i] > k)
            {                                 //人数超过2人，总权重大于k则为帮派
                g[ans].number = -p[i].parent; //保存下帮派人数
                int parent = i;               //根节点存一下，其实有点多余，可以直接用i
                int max = i;                  //权重最大者下标，初始为根节点
                for (int j = 0; j < N; j++)
                {
                    if (FindRoot(j) == parent && p[j].weight > p[max].weight)
                        max = j; //如果属于此集合且权重更大，替换一下
                }
                strcpy(g[ans].head, p[max].name); //把头目名字存进来
                ans++;                            //接着存下一个帮派
            }
        }
        printf("%d\n", ans);   //输出帮派数目
        sort(g, g + ans, cmp); //按字典sort一下
        for (i = 0; i < ans; i++)
            printf("%s %d\n", g[i].head, g[i].number); //输出头目名字和帮派人数
    }
    return 0;
}