hdu 1856 More is better

点击hdu 1856思路:
思路: 离散化+并查集
分析:
1 点数最多为10^7，但是边数最多10^5，所以我们必须采用离散化，然后利用带权并查集的思想，rank[x]表示的是以x为根节点的集合的元素个数
2 这一题主要注意的就是当n = 0的时候，因为题目说了刚开始有10^7个人在房间里面，所以n = 0的时候最多有一个人出去

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 200010;

struct Node{
    int x;
    int y;
};
Node node[MAXN];

int n , pos;
int num[MAXN];
int father[MAXN];
int rank[MAXN];

void init(){
    sort(num , num+pos);
    pos = unique(num , num+pos)-num;
    for(int i = 0 ; i <= pos ; i++){
       father[i] = i;
       rank[i] = 1;
    }
}

int search(int x){
    int left = 0;
    int right = pos-1;
    while(left <= right){
         int mid = (left+right)>>1;
         if(num[mid] == x)
             return mid+1;
         else if(num[mid] < x)
             left = mid+1;
         else
             right = mid-1;
    }
}

int find(int x){
    if(father[x] != x)
        father[x] = find(father[x]);
    return father[x];
}

int solve(){
    init();
    int ans = 0;
    for(int i = 0 ; i < n ; i++){
        int x = search(node[i].x);
        int y = search(node[i].y);
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            father[fx] = fy;
            rank[fy] += rank[fx];
            ans = max(ans , rank[fy]);
        }
    }
    return n == 0 ? 1 : ans;
}

int main(){
    while(scanf("%d" , &n) != EOF){
         pos = 0;
         for(int i = 0 ; i < n ; i++){
            scanf("%d%d" , &node[i].x , &node[i].y);
            num[pos++] = node[i].x;
            num[pos++] = node[i].y;
         }
         printf("%d\n" , solve());
    }
    return 0;
}