#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
vector<int> p(30001),rnk(30001,1),num(30001,1);
bitset<30001> visit;
int n;
int find(int a){
return p[a]==a?a:p[a]=find(p[a]);
}
bool same(int a,int b){
return find(a)==find(b);
}
void merge(int a,int b){
if(!same(a,b)){
if(rnk[find(a)]>rnk[find(b)]){
num[find(a)]+=num[find(b)];
p[find(b)]=find(a);
}
else {
num[find(b)]+=num[find(a)];
p[find(a)]=find(b);
}
if(rnk[find(a)]==rnk[find(b)])
rnk[find(b)]++;
}
}
int main(){
for(int i=1;i<=30000;i++)
p[i]=i;
cin>>n;
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
merge(x,y);
}
int mx=1,mn=30000;
for(int i=1;i<=n;i++){
if(visit[find(i)])continue;
visit[find(i)]=1;
if(num[find(i)]>mx)mx=num[find(i)];
if((num[find(i)]<mn)&&(num[find(i)]>1))mn=num[find(i)];
}
cout<<mn<<' '<<mx<<endl;
}
#include <vector>
#include <bitset>
using namespace std;
vector<int> p(30001),rnk(30001,1),num(30001,1);
bitset<30001> visit;
int n;
int find(int a){
return p[a]==a?a:p[a]=find(p[a]);
}
bool same(int a,int b){
return find(a)==find(b);
}
void merge(int a,int b){
if(!same(a,b)){
if(rnk[find(a)]>rnk[find(b)]){
num[find(a)]+=num[find(b)];
p[find(b)]=find(a);
}
else {
num[find(b)]+=num[find(a)];
p[find(a)]=find(b);
}
if(rnk[find(a)]==rnk[find(b)])
rnk[find(b)]++;
}
}
int main(){
for(int i=1;i<=30000;i++)
p[i]=i;
cin>>n;
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
merge(x,y);
}
int mx=1,mn=30000;
for(int i=1;i<=n;i++){
if(visit[find(i)])continue;
visit[find(i)]=1;
if(num[find(i)]>mx)mx=num[find(i)];
if((num[find(i)]<mn)&&(num[find(i)]>1))mn=num[find(i)];
}
cout<<mn<<' '<<mx<<endl;
}
Comments
Post a Comment