首页 > 代码库 > hdu 1856 more is better

hdu 1856 more is better

并查集基础

 

#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffffusing namespace std;int maxx;struct Children{    int coun;    int father;};Children c[10000005];int find(int a){    int temp=a;    while(temp!=c[temp].father)    {        temp=c[temp].father;    }    c[a].father=temp;    return temp;    //return c[a].father==a?a:find(c[a].father); 感觉这种写法更加简练 }void Union(int a,int b){    int x=find(a);    int y=find(b);    if(x==y) return ;    c[y].father=c[x].father;    c[x].coun+=c[y].coun;    if(maxx<c[x].coun) maxx=c[x].coun;}int main(){    int n,i,j,a,b;    while(scanf("%d",&n)!=EOF)    {        if(n==0) {cout<<1<<endl;continue;}        maxx=0;        for(i=1;i<=10000000;i++)//初始化并查集        {           c[i].coun=1;           c[i].father=i;        }        for(i=1;i<=n;i++)        {            scanf("%d%d",&a,&b);            Union(a,b);        }        printf("%d\n",maxx);    }    return 0;}