题解 | #Head of a Gang#

这题，麻烦的并查集问题，虽然能过，但代码又臭又长。。。

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<unordered_map>
using namespace std;
typedef struct node{
    string name1,name2;
    int time;
    node(string n1,string n2,int t):name1(n1),name2(n2),time(t){ }
}Node;
string find(string name,unordered_map<string,string> &mp){
    if(name != mp[name])
        mp[name] = find(mp[name],mp);
    return mp[name];
}
void Union(string name1,string name2,unordered_map<string,string> &mp,unordered_map<string, int> &temptime,int time){
    name1 = find(name1,mp);
    name2 = find(name2,mp);
    if(name1 != name2){
        if(temptime[name1] >= temptime[name2]){
            temptime[name1] += time;
            temptime[name2] = 0;
            mp[name2] = name1;
        }
        else{
            temptime[name2] += time;
            temptime[name1] = 0;
            mp[name1] = name2;
        }
    }
    else
        temptime[name1] += time;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k,time,totaltime = 0,cnt = 0;
    string name1,name2,ansname;
    unordered_map<string,string> mp;
    unordered_map<string, int> mptime,visited,temptime;
    map<string,int> ansmp;
    set<string> SetName,tempName;
    vector<Node> vec;
    while(cin >> n >> k){
        cnt = 0;
        totaltime = 0;
        mptime.clear();
        visited.clear();
        ansmp.clear();
        SetName.clear();
        temptime.clear();
        vec.clear();
        for(int i = 1;i <= n;++i){   //先形成并查集
            cin >> name1 >> name2 >> time;
            mp[name1] = name1;
            mp[name2] = name2;
            vec.push_back(Node{name1,name2,time});
            SetName.insert(name1);
            SetName.insert(name2);
            mptime[name1] += time;
            mptime[name2] += time;
        }
        for(int i = 0;i < vec.size();++i)
            Union(vec[i].name1,vec[i].name2,mp,temptime,vec[i].time);
        for(auto tp : SetName) //为了将所有的路径都压缩到一层，进行再次路径压缩
            find(tp,mp);
        for(auto it : SetName){      //遍历每个并查集，进行判断值大小
            if(visited[it] == 0 && mp[it] == it){
               ansname = it;
               visited[it] = 1;
               for(auto tp : SetName){
                   if(mp[tp] == it){
                       tempName.insert(tp);
                       visited[tp] = 1;
                       if(mptime[ansname] < mptime[tp])
                           ansname = tp;
                   }
               }
                for(auto tp : tempName)   //计算集合值
                    totaltime = max(totaltime,temptime[it]);
                if(tempName.size() >= 3 && totaltime > k){
                    cnt++;
                    ansmp[ansname] = tempName.size();
                }
                totaltime = 0;
                tempName.clear();
            }
        }
        cout << cnt << endl;
        if(cnt){
            for(auto it : ansmp)
                cout << it.first << " " << it.second << endl;
            ansmp.clear();
        }
    }
}