思路:注意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;
}