POJ 1838 Banana （并查集）

10 3
7 10
1 1
101 1
2 2
102 1
7 11
200 202
2 1
3 2
103 1

9

在一个集合里就只有当横坐标相等时，纵坐标相差为1， 或者是纵坐标相等时，横坐标差为1。 那么只需分别合并横坐标相等的，和纵坐标相等的情况。用并查集解决。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <stack>
#include <cctype>
#include <algorithm>
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
using namespace std;
typedef long long LL;
const int mod = 99999997;
const int MAX = 0x3f3f3f3f;
const int maxn = 16005;
int n, k, f[maxn], rank[maxn];
struct C {
    int x, y, id;
} in[maxn];
int Find(int x) {
    return x == f[x] ? x : f[x] = Find(f[x]);
}
bool cmp0 (C a, C b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
bool cmp1 (C a, C b) {
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}
bool cmp2 (int a, int b) {
    return a > b;
}
void Union (int p, int q) {
    int i = Find(p), j = Find(q);
    if(i == j) return;
    rank[i] += rank[j];
    f[j] = i;
    rank[j] = 0;
}
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        in[i].id = i;
        scanf("%d%d", &in[i].x, &in[i].y);
    }
    for(int i = 0; i < n; i++) rank[i] = 1, f[i] = i;
    sort(in, in+n, cmp0);
    for(int i = 0; i < n-1; i++) {
        C cur = in[i], next = in[i+1];
        if(cur.x == next.x && next.y-cur.y == 1)
            Union(cur.id, next.id);
    }
    sort(in, in+n, cmp1);
    for(int i = 0; i < n-1; i++) {
        C cur = in[i], next = in[i+1];
        if(cur.y == next.y && next.x-cur.x == 1)
            Union(cur.id, next.id);
    }
    sort(rank, rank+n, cmp2);
    int sum = 0;
    for(int i = 0; i < k; i++) sum += rank[i];
    cout << sum << endl;
    return 0;
}

POJ 1838 Banana （并查集）

原文：http://blog.csdn.net/u013923947/article/details/39063991