并查集解决团队划分问题（连通集）

总结：主要思路还是并查集，并查集的操作模板化，只用修改结构体即可

个人结点信息较多，故用结构体；

团伙由于包含人数、头目名字，且要按照字典序输出，故也用结构体

  • 个人结点：名字、通话时长
  • 团伙结点：人数、头目名字

map<string,int>Getindex： 名字→个人结点的下标，且可以判断是否为第一次出现

输入：

新人员→生成新节点

获取输入的2个人的结点下标

更新通话时长，合并

遍历：根据顶级联系人划分团伙（为减少开销，设置访问标记）

判断团伙条件

输出:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;

map<string,int>Getindex;//结点名字→数组下标（既是并查集下标，又是结构体下标）

const int maxn=2001;
int father[maxn];//并查集
int height[maxn];//高度
bool flag[maxn];//遍历标记

void Initial(int n){//初始化
  for(int i=0;i<=2*n;i++){//最多映射到1~2*n 
    father[i]=i;  
    height[i]=1;
    flag[i]=false;
  }
}

int Find(int x){
  if(x!=father[x]){
    father[x]=Find(father[x]);
  }
  return father[x];
}

void Union(int x,int y){
  int a=Find(x);
  int b=Find(y);
  if(a==b)return;
  else if(height[a]>height[b])father[b]=a;
  else if(height[a]<height[b])father[a]=b;
  else{
    father[b]=a;
    height[a]++;
  }
}

struct person{//个人结点
  string name;//名字
  int calltime;//通话总时长
  person(string a,int t):name(a),calltime(t){}
  person(){}
};

person badguy[maxn];

struct party{//团伙结点（用于输出）
  string headname;//头目名字
  int people;//人数
  bool operator <(party x)const{//为了按字典序排序
    return headname<x.headname;
  }
};

int main(){
  int n,k;
  while(scanf("%d%d",&n,&k)!=EOF){
    int i=1;//映射值从1开始
    Getindex.clear();
    Initial(n);  
    
    while(n--){//输入
      string s1,s2;
      int t;
      cin>>s1>>s2>>t;
      if(!Getindex[s1]){//映射为0即表示第一次出现
        Getindex[s1]=i;
        height[i]=1;
        badguy[i++]=person(s1,0);//生成个人结点
      }
      if(!Getindex[s2]){
        Getindex[s2]=i;
        height[i]=1;
        badguy[i++]=person(s2,0);
      }
      
      int index1=Getindex[s1];
      int index2=Getindex[s2];

      badguy[index1].calltime+=t;//累计个人通话时长
      badguy[index2].calltime+=t;
      Union(index1,index2);//合并同伙
    }

    party ans[i-1];//团伙结点数组
    int sum=0;
    int p=0;
    for(int j=1;j<i;j++){//外层：以badguy[j]初始化团伙结点信息
      if(flag[j])continue;
      flag[j]=true;
      int sumtime=badguy[j].calltime;
      int people=1;
      int maxindex=j;//临时头目下标（通话时长最长）
      
      for(int r=j+1;r<i;r++){//内层：找badguy[j]的同伙
        if(flag[r])continue;
        
        if(Find(r)==Find(j)){//相同顶级联系人
          //cout<<"member"<<badguy[r].name<<endl;
          if(badguy[r].calltime>badguy[maxindex].calltime)maxindex=r;//更新临时头目下标
          sumtime+=badguy[r].calltime;
          people++;
          flag[r]=true;
        }
      }
      
      if(sumtime>2*k&&people>2){//判断团伙条件
        sum++;
        ans[p].headname=badguy[maxindex].name;
        ans[p++].people=people;
      }
    }
    
    if(sum==0)printf("0\n");//输出
    else{
      printf("%d\n",sum);
      sort(ans,ans+p);//字典序
      for(int m=0;m<p;m++){
        cout<<ans[m].headname<<" "<<ans[m].people<<endl;
      }
    }
  }
  return 0;
}