题解 | #朋友圈#

并查集解法

• 借鉴了 @onestan 的并查集解法，封装成类，方便阅读
• 不懂并查集可以看 B 站宝藏 UP 主 @正月点灯笼 的视频讲解：并查集

#include <bits/stdc++.h>
using namespace std;

class friendsCircle
{
private:
    // curMap记录父节点，sizeMap记录该点所在朋友圈的大小，rankMap记录根节点的秩
    unordered_map<int,int> curMap, sizeMap, rankMap;
private:
    // 寻找根节点
    int findroot(int son)
    {
        while ( curMap[son]!=son ) son = curMap[son];
        return son;
    }
public:
    // 向朋友圈中插入新的朋友组合
    void append(int x, int y)
    {
        if ( curMap.find(x)==curMap.end() && curMap.find(y)==curMap.end() )
        {
            // 若插入的两点都不在朋友圈中
            curMap[x] = x;              // 更新 x 为父节点
            curMap[y] = x;              // 更新 y 为 x 的子节点
            rankMap[x] = 1;             // 更新 x 的秩
        }
        else if ( curMap.find(x)!=curMap.end() && curMap.find(y)==curMap.end() )
        {
            // 若 x 在朋友圈中， y 不在朋友圈中，将 y 更新为 x 根节点的子节点
            int xroot = findroot(x);
            curMap[y] = xroot;
        }
        else if ( curMap.find(x)==curMap.end() && curMap.find(y)!=curMap.end() )
        {
            // 若 y 在朋友圈中， x 不在朋友圈中，将 x 更新为 y 根节点的子节点
            int yroot = findroot(y);
            curMap[x] = yroot;
        }
        else
        {
            // 若 x 和 y 都在朋友圈中，根据他们根节点的秩对两个朋友圈融合
            int xroot = findroot(x);
            int yroot = findroot(y);
            if ( rankMap[xroot]>=rankMap[yroot] )
            {
                curMap[yroot] = xroot;
                rankMap[xroot] = max(rankMap[xroot], rankMap[yroot]+1);
            }
            else
            {
                curMap[xroot] = yroot;
            }
        }
    }
    // 计算最大朋友圈的大小
    int maxCircle()
    {
        int maxSize = 0;
        for (auto & it : curMap)
            maxSize = max(maxSize, ++sizeMap[findroot(it.first)]);
        return maxSize;
    }
};

int main()
{
    int T, n;
    cin >> T;
    while ( T-- )
    {
        cin >> n;
        friendsCircle FRDC;
        int x, y;
        while ( n-- )
        {
            cin >> x >> y;
            FRDC.append(x,y);
        }
        cout << FRDC.maxCircle() << endl;
    }
    return 0;
}