並查集(Disjoint Set) 模板

並查集(Disjoint Set)：就是指有很多集合的意思(裡面的元素只有一個)，簡稱並查集

那我們就開一個p[]陣列，p[i]代表元素i在哪個集合裡面(若p[i]==i則自己在自己的集合)

要尋找集合的頭，就一直遞回，直到p[i]==i

要合併的話，就把兩個群組的頭互相接在一起

這樣的複雜度是O(N^2)

加速的話，請詳見code，最後會變成O(alpha(N)) = O(1)

模板題：http://poj.org/problem?id=2236

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

const int MAX_N = 1010;

inline int get_dis(int x1,int y1,int x2,int y2) {
    return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
}

vector<int> chudu[MAX_N];
bool repair[MAX_N];

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

inline int get_Dis(Node n1, Node n2) {
    return get_dis(n1.x,n1.y,n2.x,n2.y);
}

void get_chudu(int n,int d) {
    for (int i=1;n>=i;i++) {
        for (int j=i+1;n>=j;j++) {
            if (get_Dis(node[i],node[j])<=d*d) {
                chudu[i].push_back(j);
                chudu[j].push_back(i);
            }
        }
    }
}

struct DisjointSet {
    int p[MAX_N];
    int rank[MAX_N];
    void init(int i) {
        for (int x=1;i>=x;x++) p[x]=x,rank[x]=1;
    }
    int Find(int x) {
        return p[x]==x?x:p[x]=Find(p[x]);
    }
    void Union(int x,int y) {
        if (rank[Find(x)]>rank[Find(y)]) {
            p[Find(x)] = Find(y);
            rank[Find(y)]+=rank[x];
        }
        else {
            p[Find(y)] = Find(x);
            rank[Find(x)]+=rank[y];
        }
    }
} djs;

int main () {
    int n,d;
    scanf("%d %d",&n,&d);
    for (int x=1;n>=x;x++) {
        scanf("%d %d",&node[x].x,&node[x].y);
    }
    get_chudu(n,d);
    djs.init(n);
    char D;
    while (cin >> D) {
        if (D=='O') {
            int i;
            scanf("%d",&i);
            repair[i]=true;
            int len=chudu[i].size();
            for (int x=0;len>x;x++) {
                int tmp=chudu[i][x];
                if (repair[tmp]==true) djs.Union(i,tmp);
            }
        }
        else {
            int i,j;
            scanf("%d %d",&i,&j);
            if (djs.Find(i)==djs.Find(j)) puts("SUCCESS");
            else puts("FAIL");
        }
    }
}