今天开始学算法系列 -- 并查集

     并查集的原理可以google 很多，比较简单。这里主要记录下自己的实现。
     一个典型的应用是在kruskal算法中
    直接上代码：
    

#define MAXN 7
int ID[MAXN] = { 0 };
int rank[MAXN];
class union_find
{
public:
    union_find();
    int find_root(int x);
    void connect(int x, int y);
    bool isConnected(int x, int y);
};

bool union_find::isConnected(int x, int y)
{
    int xRoot = find_root(x);
    int yRoot = find_root(y);
    if (xRoot == yRoot)
    {
        printf("Has Connected\n");
        return true;
    }
    else
        return false;
}


union_find::union_find()
{
    for (int i = 0; i < MAXN; i++)
    {
        ID[i] = i;
        rank[i] = 1;
    }
}

int union_find::find_root(int x)
{
    if (ID[x] == x)
        return x;
    return find_root(ID[x]);
}

void union_find::connect(int x, int y)
{
    int xRoot = find_root(x);
    int yRoot = find_root(y);
    if (xRoot == yRoot)
    {
        printf("Has Connected\n");
        return;
    }
    if (rank[xRoot] >= rank[yRoot])
    {
        rank[xRoot] += 1;
        ID[yRoot] = ID[xRoot];
    }
    else
    {
        rank[yRoot] += 1;
        ID[xRoot] = ID[yRoot];
    }
}


int _tmain(int argc, _TCHAR* argv[])
{
    union_find m;
    m.connect(ID[0], ID[1]);
    m.connect(ID[2], ID[1]);
    m.connect(ID[3], ID[4]);
    if (m.isConnected(ID[3], ID[4]))
    {
        printf("connected\n");
    }
    return 0;
}