【并查集】hdu 1856 More is better

题目描述：

http://acm.hdu.edu.cn/showproblem.php?pid=3635

 

中文大意：

王先生需要在一千万人中，寻找一些人帮他做项目。

要求所选人群中，任何两个人之间都是朋友关系（直接或间接），或者只选一个人。

问最多能选几个人。

 

思路：

并查集的基本题型，但不同的是，这次 n 的范围很大，所以需要加一些限制，避免超内存。

 

代码：

#include<iostream>
using namespace std;
#define MAX 10000020

int friends[MAX];
int cnt[MAX];
int n,max_num;

void init(){
    for (int i=1;i<MAX;i++) {
        friends[i] = 0;
        cnt[i] = 1;
    }
} 

int find(int x){
    if(friends[x] == 0){
        return x;
    }
    friends[x] = find(friends[x]);
    return friends[x];
}

void union_set(int x, int y){
    x = find(x);
    y = find(y);
    
    //不加这个条件，会超内存 
    if(x == y){
        return;
    }
    //简单优化 
    if(cnt[x] <= cnt[y]){
        friends[x] = y;
        cnt[y] += cnt[x];
        max_num = (max_num > cnt[y])?max_num:cnt[y];
    }
    else{
        friends[y] = x;
        cnt[x] += cnt[y];
        max_num = (max_num > cnt[x])?max_num:cnt[x];
    }
}

int main(){
    while(~scanf("%d", &n)){
        init();
        max_num = 1;
        
        int x,y;
        for(int i=0;i<n;i++){
            scanf("%d %d", &x, &y);
            union_set(x, y);
        }
        printf("%d
", max_num);
    }
}