题解 | #Head of a Gang#

#include <iostream>
#include <map>
using namespace std;
const int maxn=100;
int father[maxn];
int height[maxn];
int weight[maxn];
int gangnum[maxn];
int findfather(int x){
    if(father[x]!=x) father[x]=findfather(father[x]);
    return father[x];
}
void swap(int& a,int& b){
    int tem=a;
    a=b;
    b=tem;
}
void Union(int x,int y){
    int fx=findfather(x);
    int fy=findfather(y);
    if(height[fx]<height[x]){
        father[fx]=x;
        father[x]=x;
        fx=x;
    }
    if(height[fy]<height[y]){
        father[fy]=y;
        father[y]=y;
        fy=y;
    }
    if(height[fx]>height[fy]) father[fy]=fx;
    else father[fx]=fy;
}
map<string,int> namebook1;
map<int,string> namebook2;
map<string,int> gangs;
int order;
void init(){
    namebook1.clear();
    namebook2.clear();
    gangs.clear();
    for(int i=0;i<maxn;i++){
        father[i]=i;
        height[i]=0;
        weight[i]=0;
        gangnum[i]=0;
    }
    order=0;
}
int rigister(string x){
	if(namebook1.find(x)==namebook1.end()  ) {
		namebook1[x]=order++;
	}
	return namebook1[x];
	
} 
int main(){
    int n,k;
    while(cin>>n>>k){
        init();
        for(int i=0;i<n;i++){
        string a,b;
        int phonetime;
        cin>>a>>b>>phonetime;
        int anum=rigister(a);
        int bnum=rigister(b);
        namebook2[anum]=a;
        namebook2[bnum]=b;
        height[anum]+=phonetime;
        height[bnum]+=phonetime;
        weight[anum]+=phonetime;
        Union(anum,bnum);
    }
        for(int i=0;i<order;i++){
            findfather(i);
            if(i!=father[i]) weight[father[i]]+=weight[i];
            gangnum[father[i]]++;
        }
        for(int i=0;i<order;i++){
            if(gangnum[i]>2 && weight[i]>k){
                string head=namebook2[i];
                gangs[head]=gangnum[i];
            }
        }
        cout<<gangs.size()<<endl;
        for(map<string,int> ::iterator i=gangs.begin();i!=gangs.end()
        ;i++){
            cout<<i->first<<' '<<i->second<<endl;
        }
    }
    
}