会python真的可以为所欲为0(回)
395天前
这里还有人吗1(回)
580天前这里还有人吗0(回)
580天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
805天前到处都是羊，不想上班0(回)
885天前
鸽子
0(回)
889天前#include<iostream> |
#include<cstdio> |
#include<cstring> |
#include<algorithm> |
const int MAX=10000001; |
int father[MAX];//父节点 |
int friend_X[MAX];//朋友数 |
int Max;//最大朋友数 |
using namespace std; |
void init() |
{ |
int i; |
for(i=1;i<MAX;++i) |
father[i]=i,friend_X[i]=1;//朋友数初始化都是1 |
} |
int find_father(int x)//这里用递归省时，因为用while会超时，因为条件给的范围是一千万 |
{ |
if(x!=father[x])//寻找父节点 |
father[x]=find_father(father[x]); |
return father[x]; |
/*while(x!=father[x])//这里超时过一次，以后碰到数据大的最好不要用while |
{ |
x=father[x]; |
} |
return x;*/ |
} |
void join_tree(int x,int y) |
{ |
int a,b; |
a=find_father(x); |
b=find_father(y); |
if(a!=b) |
{ |
father[a]=b;//把新的子节点并进父节点 |
friend_X[b]+=friend_X[a];//每次父节点都加上新的子节点的朋友数 |
if(friend_X[b]>Max)//挑选最大的父节点朋友数 |
Max=friend_X[b]; |
} |
} |
int main() |
{ |
int t,x,y,sum; |
while(cin>>t) |
{ |
init(); |
Max=1;//这里初始化是1不是0，因为当输入时0时，输出是1，就是这样我WA了一次 |
while(t--) |
{ |
cin>>x>>y; |
join_tree(x,y);//每次更新节点 |
} |
cout<<Max<<endl; |
} |
return 0; |
} |
