2926问题 C: 团伙(group)

题目描述

在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：

1、我朋友的朋友是我的朋友；

2、我敌人的敌人是我的朋友；

所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

输入

第1行为n和m，1<n<1000,1≤m≤100 000；

以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。

输出

一个整数，表示这n个人最多可能有几个团伙。

样例输入

6 4

1 1 4

0 3 5

0 4 6

1 1 2

样例输出

3

思路

这是并查集的一种运用，首先我们先将所有父节点初始化为他们自己；

如果输入的两人是朋友，则进入并集函数，如果两人是敌人，则分别与对方的敌人并集，并记录各自的敌人数量；

最后遍历所有人，只要他的父节点是他自己便是根节点，而我们只需找到所有的根节点即为所有的团体数

代码：

#include<bits/stdc++.h>

using namespace std;

int tuan[100001],di[1001][1001];//tuan用来记录团伙,di[i][j]用来存储i的第j个敌人

int find(int x)//查集函数

{

       if(tuan[x]!=x)

       tuan[x]=find(tuan[x]);

       return tuan[x];

}

void unionn(int r1,int r2)

{

       tuan[r2]=r1;//团伙的并集

}

int main()

{

       int n,m;

       cin>>n>>m;

       for(int i=1;i<=n;i++)

       tuan[i]=i;//先将所有父节点定为他们自己

       for(int i=1;i<=m;i++)

       {

              int p,x,y;

              cin>>p>>x>>y;

              if(p==0)//p==0时他们是朋友，所以并集

              {

                     if(find(x)!=find(y))

                     unionn(find(x),find(y));

              }

              Else//p==1时他们是敌人，将敌人的敌人并集

              {

                     for(int j=1;j<=di[x][0];j++)

                     {

                            if(find(y)!=find(di[x][j]))

                            unionn(find(y),find(di[x][j]));

                     }     

                     for(int j=1;j<=di[y][0];j++)

                     {

                            if(find(x)!=find(di[y][j]))

                            unionn(find(x),find(di[y][j]));

                     }

                     di[y][0]++;//记录敌人的个数

                     di[y][di[y][0]]=x;

                     di[x][0]++;

                     di[x][di[x][0]]=y;

                    

              }

        }

        int a=0;//要找到集合的个数，只需找到根节点的个数，a用来记录根节点的个数

       for(int i=1;i<=n;i++)

       if(tuan[i]==i) //当父节点就是自己本身时，就是那个集合的根节点

       a++;

       cout<<a<<endl;

}