Reiks的技术博客

C/C++/STL/Algorithm/D3D
posts - 17, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

并查集

Posted on 2009-08-28 10:34 reiks 阅读(436) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构
#define MAXSIZE 50001
int father[MAXSIZE];
int rank[MAXSIZE];

void initial()
{
    memset(rank, 0, sizeof(rank));
    for ( int i = 0; i < MAXSIZE; ++i )
        father[i] = -1;
}

int find_set(int x)
{
    int r = x, q;

    while(father[r] != -1)
    {
        r = father[r];
    }

    while(x != r)
    {
        q = father[x];
        father[x] = r;
        x = q;
    }
    return r;
}

void union_set(int x, int y)
{
    int a = find_set(x);
    int b = find_set(y);
    if (a == b)
        return;
    if (rank[a] > rank[b])
    {
        father[b] = a;
    }
    else
    {
        father[a] = b;
        if (rank[a] == rank[b])
        {
            ++rank[b];
        }
    }
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理