HDU 1856 More is better（并查集+离散化）

题目地址：HDU 1856

水题。由于标号范围太大，而数据数只有10w，所以要先进行离散化。然后就是裸的并查集了。

代码如下：

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
int bin[100001], x[100001], y[100001], z[200001], c[200001], cnt, vis[200000];
int find1(int x)
{
    return bin[x]==x?x:bin[x]=find1(bin[x]);
}
void merger(int x, int y)
{
    int f1=find1(bin[x]);
    int f2=find1(bin[y]);
    if(f1!=f2)
        bin[f2]=f1;
}
int twofen(int x)
{
    int high=cnt-1, low=0, mid;
    while(low<=high)
    {
        mid=low+high>>1;
        if(c[mid]==x) return mid;
        else if(c[mid]<x) low=mid+1;
        else high=mid-1;
    }
}
int main()
{
    int n, i, max1, a, b, f1, f2;
    while(scanf("%d",&n)!=EOF)
    {
        cnt=1;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
            z[2*i]=x[i];
            z[2*i+1]=y[i];
        }
        sort(z,z+2*n);
        c[0]=z[0];
        for(i=1;i<2*n;i++)
        {
            if(z[i]!=z[i-1])
                c[cnt++]=z[i];
        }
        for(i=0;i<cnt;i++)
            bin[i]=i;
        for(i=0;i<n;i++)
        {
            f1=twofen(x[i]);
            f2=twofen(y[i]);
            merger(f1,f2);
        }
        memset(vis,0,sizeof(vis));
        max1=-1;
        for(i=0;i<cnt;i++)
        {
            int p=find1(bin[i]);
            vis[p]++;
            if(max1<vis[p])
                max1=vis[p];
        }
        printf("%d\n",max1);
    }
    return 0;
}