hdu 1856 More is better

简介: 点击hdu 1856思路: 思路: 离散化+并查集 分析: 1 点数最多为10^7,但是边数最多10^5,所以我们必须采用离散化,然后利用带权并查集的思想,rank[x]表示的是以x为根节点的集合的元素个数 2 这一题主要注意的就是当...

点击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;
}


目录
相关文章
|
Java 测试技术
hdu 1228 A + B
hdu 1228 A + B
56 0
HDU2203亲和串
博客水平见水平......目前阶段就是这么菜,我会好好努力的!毕业直接拿到阿里offer!
1231 0
|
机器学习/深度学习 算法
|
定位技术
hdu 4771 Stealing Harry Potter's Precious
点击打开链接 题意:题目给定一个n*m的地图,地图有一个起点标记为'@',还有'#'表示不能够走的,'.'表示可以走。给定k个点,问从起点开始把这k个点走过去的最小步数。
794 0