7-25 朋友圈 (25分)--并查集

参考

主要思路：

1.将每个学生视为树的一个结点，用一个数组存储每个结点的前驱结点，当只有一个单独的学生的时候，将前驱设为他本身。然后每行第一个学生a与这一行的其余学生b1、b2……bn分别作合并操作，即a所在的树与bn所在的树相比较，将深度小的那一棵树的根节点x前驱设为深度大的那一棵树的根节点y，这样，两棵树就合在一起了，这样a和bn以及他们之前所在树的所有结点的根结点都变为了y，在判断是不是朋友的时候，只需要判断他们的根节点相不相同即可。

2.深度小的树合并到深度大的树，深度大的树的深度并没有增加。

3.深度相同的两棵树合并，深度为比原来增加1。

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int r[30001] = {0};//储存每个结点的前驱
int depth[30001] = {0};//储存树的深度，假设一个结点时深度为0
int find(int k)//查找出根节点
{
    int root = k;
    while (root != r[root])
    {
        root = r[root];
    }
    return root;
}
void merge(int a, int b)
{
    int x = find(a),y=find(b);
    if(x < y)
    {
        r[x] = y;
    }
    else if(y < x)
    {
        r[y] = x;
    }
    else if(x == y && x!=y)
    {
        r[x] = y;
        depth[y]++;
    }
}
int main()
{
    int c[30001] = {0};
    int n1, n2;
    cin >> n2 >> n1;
    for(int i=0;i<=n2;i++)r[i]=i;//初始化，把每个单独的结点看成一棵树，所以前驱设为自己
    for (int i = 0; i < n1; i++)
    {
        int n;
        cin >> n;
        int f;
        for (int j = 0; j < n; j++)
        {
            int t;
            cin >> t;
            if(j==0) f=t;//f储存第一个输入的结点
            merge(t,f);
        }
    }
    int max_ = 0;
    for (int i = 1; i <= n2; i++)
    {
            int t = ++c[find(i)];
              if (max_ < t)
            max_ = t;
    }
    cout << max_ << endl;
    return 0;
}