专栏首页calmoundMore is better(并查集)

More is better(并查集)

#include<stdio.h>
#include<string.h>
const int MAXN=10000010;
int father[MAXN],hash[MAXN];

void Make_set()
{
    for(int i=0;i<MAXN;i++)
    {
        father[i]=i;
        //rank[i]=0;
    }
}

int Find(int x)
{
    int r=x;
    while(r!=father[r])
    {
        r=father[r];
    }
    if(r!=x) father[x]=r;
    return father[x];
}

void Union(int x,int y)
{
    if(x==y) return ;
   /* if(rank[x]>rank[y]) father[y]=x;
    else
    {
        if(rank[x]==rank[y])
        {
            rank[y]++;
        }
        father[x]=y;
    }*/
    father[x]=y;
}

int main()
{
    int T,i,n,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        memset(hash,0,sizeof(hash));
        Make_set();
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            int x=Find(a);
            int y=Find(b);
            Union(x,y);
        }
        int mx=0;
        for(i=1;i<MAXN;i++)
        {
            hash[Find(father[i])]++;
        }
        for(i=1;i<MAXN;i++)
        {
            if(mx<hash[i]) mx=hash[i];
        }
        printf("%d\n",mx);
    }
    return 0;
}
#include <iostream>
using namespace std;
const int maxn=10000010;
int    n;
struct NODE
{
    int root;
    int num;
}nod[maxn];

struct SEG
{
    int u, v;
}seg[100001];

int u, v;
int maxsum;

int getfather(int r)
{
    if(nod[r].root==-1)
    return r;
    int temp = nod[r].root;
    nod[r].root=getfather(temp);
    return nod[r].root;
}

void union_set(int r1, int r2)
{
    int root1=getfather(r1);
    int root2=getfather(r2);
    nod[root1].root=root2;
    nod[root2].num += nod[root1].num;
    if(nod[root2].num>maxsum)
    {
        maxsum=nod[root2].num;
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        maxsum=1;
        for (int i=1; i<=n; i++)
        {
              scanf("%d %d",&seg[i].u, &seg[i].v);
              nod[ seg[i].u ].root = -1;
              nod[ seg[i].u ].num=1;
              nod[ seg[i].v ].root =-1;
              nod[ seg[i].v ].num = 1;
        }
        for (int i=1; i<=n; i++)
        {
            if(getfather(seg[i].u)!=getfather(seg[i].v))
            {
                union_set(seg[i].u, seg[i].v);
            }
        }
        printf("%d\n", maxsum);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 2011 菜鸟杯

    A:该题写了很久,一直TLE,主要是枚举到n/2时间复杂度实在太高了,其实嘛,这道题就是因式分解,所以就是i*i=n,也就是sqrt(n) #include<s...

    用户1624346
  • zoj 2521 LED Display

    题意:开灯,每个数字都由好几个灯组成,其中一些数字灭掉某些灯可以成为另一个数字,如0灭掉3个灯可以变成7,         现给你一组数字,如何组合可以形成最少...

    用户1624346
  • Sicily 8843 Ranking and Friendship

    http://soj.me/8843 题意:几个人想做好朋友,朋友之间相差位置小于等于k,且长度相同 分析;排序,将长度相同的放在一起。若长度相同,第i个人能放...

    用户1624346
  • BZOJ4518: [Sdoi2016]征途(dp+斜率优化)

    Description Pine开始了从S地到T地的征途。 从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。 Pine计划用m天到达T地。除第m...

    attack
  • hdoj 4554 叛逆的小明

    xindoo
  • 斐波那契数列的若干解法

    无道
  • c++之内存模型

    堆区:由程序员分配释放,若程序员不释放,则程序结束时由系统释放。在c++中主要利用new在堆区开辟内存。

    绝命生
  • HDU1878 欧拉回路

    Problem Description 欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路? Inp...

    attack
  • 算法和数据结构: 十二 无向图相关算法基础

    从这篇文章开始介绍图相关的算法,这也是Algorithms在线课程第二部分的第一次课程笔记。

    yaphetsfang
  • 7-1 二分查找 (20分)

    输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x,使用二分查找算法查找x,输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和...

    韩旭051

扫码关注云+社区

领取腾讯云代金券