HDOJ1856

[c++]代码库

#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;
}