题目链接
我们要求的是在同一棵树上最多的人，所以用到带权并查集，将所有的人数存进根节点中。
好久不写带权并查集了，补下。
对了，这道题还要离散化思想一下，不然1e9的数据还真不好跑。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN=200005;
int N, dian, has[maxN];
int cnt[maxN], root[maxN];
map<int, int> mp;
void init()
{
mp.clear();
for(int i=1; i<maxN; i++) { root[i]=i; cnt[i]=1; has[i]=0; }
dian=0;
}
int fid(int x)
{
if(root[x] == x) return x;
return root[x]=fid(root[x]);
}
void mix(int x, int y)
{
int u=fid(x), v=fid(y);
if(u!=v)
{
root[u]=v;
cnt[v]+=cnt[u];
}
}
int main()
{
while(scanf("%d", &N)!=EOF)
{
init();
for(int i=1; i<=N; i++)
{
int e1, e2;
scanf("%d%d", &e1, &e2);
if(!mp[e1]) mp[e1]=++dian;
if(!mp[e2]) mp[e2]=++dian;
mix(mp[e1], mp[e2]);
}
int ans=1;
for(int i=1; i<=dian; i++)
{
ans=max(ans, cnt[i]);
}
printf("%d\n", ans);
}
return 0;
}
