思路：注意n为0的时候输出1，还有内存。这题是数据水了，要不我的Count[ ]数组，开10^5绝对会WA。离散化还没想清楚，想清楚了再更新代码。【水过代码下面是正经的AC代码，其实这道题不用离散化，因为即使离散化还是要开多两个10^7的数组，之前就是因为酱紫MLE了，后来只是改变了路径压缩的方式，把原本的记录高度改成记录树里的节点数，道理是一样的，不会退化。还省了点内存。】
下面是水过的AC代码：
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 10000009
int par[maxn], h[maxn], n, Count[maxn/100];
bool vis[maxn];
void init()
{
for(int i = 0; i < maxn; i++) {
par[i] = i;
vis[i] = false;
h[i] = 0;
if(i < maxn/100)
Count[i] = 0;
}
}
bool cmp(int a, int b)
{
return a > b;
}
int Find(int x)
{
if(par[x] == x) return x;
return par[x] = Find(par[x]);
}
void Union(int a, int b)
{
a = Find(a);
b = Find(b);
if(h[a] > h[b]) par[b] = par[a];
else{
if(h[a] == h[b]) h[b]++;
par[a] = par[b];
}
}
void work()
{
for(int i = 0; i < n; i++){
int a, b;
scanf("%d%d", &a, &b);
Union(a, b);
vis[a] = vis[b] = true;
}
for(int i = 0; i < maxn; i++)
if(vis[i]) {
int p = Find(i);
Count[p]++;
}
sort(Count,Count+maxn/100,cmp);
cout<<Count[0]<<endl;
}
int main()
{
while(scanf("%d", &n) != EOF){
if(n != 0){
init();
work();
}
else cout<<"1"<<endl;
}
return 0;
}
AC代码II：
//AC
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 10000009
int par[maxn],child_num[maxn], Max, n;
void init()
{
for(int i = 0; i < maxn; i++) {
par[i] = i;
child_num[i] = 1;
}
Max = 0;
}
int Find(int x)
{
if(par[x] == x) return x;
return par[x] = Find(par[x]);
}
void Union(int a, int b)
{
a = Find(a);
b = Find(b);
if(a != b)
if(child_num[a] > child_num[b]) {
par[b] = par[a];
child_num[a] += child_num[b];
if(Max < child_num[a]) Max = child_num[a];
}
else{
child_num[b] += child_num[a];
par[a] = par[b];
if(Max < child_num[b]) Max = child_num[b];
}
}
void work()
{
for(int i = 0; i < n; i++){
int a, b;
scanf("%d%d", &a, &b);
Union(a, b);
}
cout<<Max<<endl;
}
int main()
{
while(scanf("%d", &n) != EOF){
if(n != 0){
init();
work();
}
else cout<<"1"<<endl;
}
return 0;
}
