通过并查集求亲戚数量

某城市有n个人，现对n个人从1到n编号，并形成m个大家庭。每个大家庭形成一个亲戚圈。一个人可以同时属于若干个不同的家庭。（例如小明既属于他爷爷的家庭属于他外公的家庭），根据“我的亲戚的亲戚也是我的亲戚”这个推论可以得出，如果A和B是亲戚，且B和C是亲戚，则A和C也是亲戚。
猜一猜最大的亲戚圈中有多少人。

输入
第一行包含两个正整数n,m，中间用空格隔开
余下m行，第一个数表示该家庭的人数，后面表示家庭成员

输出
输出给出一个整数，表示在最大亲戚圈中有多少人。

样例输入
7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

样例输出
4

提示
n≤30000
m≤1000
这样的输入要怎么来合并啊，还有怎么求并查集集合的最大数量啊

用一个二维数组记录每个人的关系，每一行中的非0元素就代表该人的亲戚数。

代码如下：

#include <iostream>
using namespace std;
//#define N 30000
#define M 1000
int main()
{
    char **a;//[N][N]={0}; //a存储所有的关系，a[i]记录的是跟i人有关系的所有人
    int b[M]={0};
    int n,m,i,j,k;
    cin >>n >>m;
    a = new char*[n];
    for(i=0;i<n;i++)
    {
        a[i] = new char[n];
        memset(a[i],0,n);
    }
    //处理二维数组
    for (i=0;i<m;i++)
    {
        cin >> k;
        for(j=0;j<k;j++)
            cin >> b[j];
        //构建关系网
        int p,q;
        for(p=0;p<k;p++)
        {
            for(q=p+1;q<k;q++)
            {
                a[b[p]-1][b[q]-1] = 0x01; 
                a[b[q]-1][b[p]-1] = 0x01; 
            }
        }
    }

    //处理间接关系
    for (i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(a[i][j] ==0x01)
            {
                //找j对应的关系
                for(int t=0;t<n;t++)
                {
                    if(a[j][t]==0x01)
                        a[i][t] = 0x01;
                }
            }
        }
    }


    //统计数组a中每一行中1的个数
    int maxnmb = 0;
    for (i=0;i<n;i++)
    {
        int tt = 0;
        for(j=0;j<n;j++)
        {
            if(a[i][j]==0x01)
                tt++;
        }
        if(tt>maxnmb)
            maxnmb = tt;
    }
    cout << maxnmb;

    //释放空间
    for (i=0;i<n;i++)
    {
        delete[] a[i];
        a[i] = 0;
    }
    delete[] a;
    a = 0;
    return 0;
}

可以用并查集实现：

#include <iostream>
#include <vector>

using namespace std;

class UnionFind
{
public:
    UnionFind(int n)
    {
        families.resize(n+1);
        relatives.resize(n+1);
        for(int i=0;i<n+1;i++)
        {
            families[i] = i;
            relatives[i] = 0;
        }
    }

    void Union(vector<int> &members)
    {
        int x=Find(members[0]), y=0;
        for(int i=1;i<members.size();i++)
        {
            y = Find(members[i]);
            families[y] = x;
        }
    }
    
    int Find(int i)
    {
        int temp_i=i;
        while(families[i]!=i)
        {
            i = families[i];
        }
        families[temp_i]=i;//路径压缩
        return i;
    }
    
    int GetMaxGroup()
    {
        int maxmembers=0, x=0;
        for(int i=1;i<families.size();i++)
        {
            x=Find(i);
            relatives[x]+=1;
            if(relatives[x]>maxmembers)
            {
                maxmembers = relatives[x];
            }
        }
        return maxmembers;
    }
    
    void Print()
    {
        cout<<"families: "<<endl;
        for(int i=1;i<families.size();i++) cout<<families[i]<<' ';
        cout<<endl;
        cout<<"relatives: "<<endl;
        for(int i=1;i<relatives.size();i++) cout<<relatives[i]<<' ';
        cout<<endl;
    }
private:
    vector<int> families;
    vector<int> relatives;
};

int main()
{
    int n,m,num;
    vector<int> members;
    
    cin>>n>>m;
    UnionFind uf(n);
    for(int i=0;i<m;i++)
    {
        cin>>num;
        members.resize(num);
        for(int j=0;j<num;j++)
        {
            cin>>members[j];
        }
        uf.Union(members);
    }
    cout<<uf.GetMaxGroup()<<endl;
    //uf.Print();
    return 0;
}