并查集

1. 建图
2. 得到并查集
3. 遍历帮派，通过 vecter 记录信息
4. 遍历帮派成员
5. 输出

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int N = 27*27*27;

int p[N], h[N], weight[N];
bool st[N];

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    p[a] = b;
    h[b] ++;
}

void init()
{
    for(int i = 0; i <= N; i++){
        p[i] = i;
        st[i] = false;
        weight[i] = 0;
    }
}

int main()
{
    int n, k;
    while(cin >> n >> k){
        init();
        int len = 3;
        while(n--){
            string a, b; int w;
            cin >> a >> b >> w;
            int c, d;
            if(a.size() == 1){
                len = 1;
                a += "AA";
                b += "AA";
            }  
            if(a.size() == 2){
                len = 2;
                a += "A";
                b += "A";
            } 
            c = (a[0] - 'A' + 1) * 27*27 + (a[1] - 'A' + 1) * 27 + (a[2] - 'A' + 1);
            d = (b[0] - 'A' + 1) * 27*27 + (b[1] - 'A' + 1) * 27 + (b[2] - 'A' + 1);
            merge(c, d);
            weight[c] += w; weight[d] += w;
        }
        int flag = 0;
        vector<string> name;
        vector<int> num;
        for(int i = 1; i <= N; i++){
            if(h[i] == 0) continue;
            string q;
            q.append(1, 'A'+i/27/27-1);
            q.append(1, i/27%27-1+'A');
            q.append(1, i%27-1+'A');
            int root = find(i);
            if(!st[root]){
                st[root] = true;
                q.append(1, 'A'+root/27/27-1);
                q.append(1, root/27%27-1+'A');
                q.append(1, root%27-1+'A');
                int sum = 0, max = 0, cnt = 0, idx = 0;
                for(int j = 1; j <= N; j++){
                    if(find(j) == root){
                        q.append(1, 'A'+j/27/27-1);
                        q.append(1, j/27%27-1+'A');
                        q.append(1, j%27-1+'A');
                        cnt ++;
                        sum += weight[j];
                        idx = (weight[j] > max)? j : idx;
                        max = (weight[j] > max)? weight[j] : max;
                    }
                }
                if(sum/2 > k && cnt > 2){
                    flag ++;
                    num.push_back(cnt);
                    string q;
                    q.append(1, 'A'+idx/27/27-1);
                    q.append(1, idx/27%27-1+'A');
                    q.append(1, idx%27-1+'A');
                    name.push_back(q);
                }
            }   
        }
        if(!flag) cout << "0" << endl;
        else{
            cout << flag << endl;
            for(int i = 0; i < flag; i++){
                cout << name[i].substr(0, len) << " " << num[i] << endl;
            }
        }
    }
    return 0;
}