题解 | #朋友圈#

并查集，对这一知识点不太清楚的小伙伴可以看看这篇文章：并查集。 细节见代码注释

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


int main()
{
    int T;
    cin>>T;
    int n,x,y,maxsize,havex,havey,xfather,yfather;
    unordered_map<int,int> thismap,sizemap,rankmap;//分别标记父节点，集合节点数，集合秩
    for(int i=0;i<T;++i)
    {
        cin>>n;
        maxsize=0;
        thismap.clear();
        sizemap.clear();
        rankmap.clear();
        for(int j=0;j<n;++j)
        {
            cin>>x>>y;
            havex=thismap.find(x)!=thismap.end();
            havey=thismap.find(y)!=thismap.end();
            if(!havex&&!havey)//情况一：x,y都不在任何一个并查集中
            {
                thismap[x]=x;//新建一个并查集x，x的父节点为他自身
                thismap[y]=x;//将y加入
                rankmap[x]=1;//秩为1
            }
            else if(havex&&!havey)//情况二：x在某个集合中，而y不在任何一个并查集中
            {
                xfather=x;
                while(xfather!=thismap[xfather])xfather=thismap[xfather];//先找到x所在集合的根节点xfather
                thismap[y]=xfather;//将y加入
            }
            else if(havey&&!havex)//情况三：y在某个集合中，而x不在任何一个并查集中,与情况二同理
            {
                yfather=y;
                while(yfather!=thismap[yfather])yfather=thismap[yfather];
                thismap[x]=yfather;
            }
            else//情况四:x,y都已经在某个集合中
            {
                xfather=x;
                yfather=y;
                while(xfather!=thismap[xfather])xfather=thismap[xfather];
                while(yfather!=thismap[yfather])yfather=thismap[yfather];//首先找到x和y的根节点xfather和yfather
                if(xfather!=yfather)//如果x和y不在同一个集合，将两个集合按秩合并（秩小的集合合并到秩大的集合里）
                {
                    if(rankmap[xfather]>=rankmap[yfather])
                    {
                        thismap[yfather]=xfather;
                        rankmap[xfather]=max(rankmap[xfather], rankmap[yfather]+1);//更新秩值
                    }
                    else thismap[xfather]=yfather;
                }
            }
        }
        for(auto r=thismap.begin();r!=thismap.end();++r)//遍历每个元素，统计每个集合元素个数
        {
            xfather=r->first;
            while(xfather!=thismap[xfather])xfather=thismap[xfather];
            ++sizemap[xfather];
        }
        for(auto r=sizemap.begin();r!=sizemap.end();++r)//遍历每个集合，记录元素最多的集合元素数量
        maxsize=max(maxsize,r->second);
        cout<<maxsize<<endl;
    }
    return 0;
}