点击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;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
HDU最全ac代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类
Hdu 1237 解题代码
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码