浅析Connectivity Problem

问题描述
已知一个整数对(pair)序列，每个整数代表一个对象，将p-q解释成p与q连通。连通是可传递的，例如p与q连通，q与r连通，则p与r连通。写一段程序，从集合中过滤多余的连接对。即当输入一个对p-q，仅当程序不能通过可传递性证明p与q连通时，才输出该对。

代码示例
快速查找 quick-find

view plain
/* Connectivity
* quick-find
* 慢速并集
*/
#include <stdio.h>
#define N 1000
int main(void)
{
    int i, p, q, t, id[N];
    for(i = 0; i < N; i++)
        id[i] = i;
    while(scanf("%d %d", &p, &q) == 2)
    {
        if(id[p] == id[q]) continue;        //连通，进入下个循环
        for(t = id[p], i = 0; i < N; i++)   //所有id与id[p]比较，赋值给t防止id[p]被覆盖
            if(id[i] == t) id[i] = id[q];//更新连通对的id
        printf("output: %d %d\\n", p, q);
    }
    return 0;
}
快速并集 quick-union

view plain
/* 连通性问题 Connectivity
* 快速并集 quick-union
*
*/
#include <stdio.h>
#define N 1000
int main(void)
{
    int i, j, p, q, t, id[N];
    for(i = 0; i < N; i++)
        id[i] = i;
    while(scanf("%d %d", &p, &q) == 2)
    {
        for(i = p; i != id[i]; i = id[i]);    //寻找p对应的根节点
        for(j = q; j != id[j]; j = id[j]);    //根节点判断，i==id[i]
        if(i == j) continue;                  //已连通，进入下个循环
        id[i] = j;                            //修改p的根节点指向q的根节点
        printf("output: %d %d\\n", p, q);
    }
    return 0;
}
加权快速并集 weighted-quick-union

view plain
/* 连通性问题 Connectivity
* 加权快速并集 weighted-quick-union
*
*/
#include <stdio.h>
#define N 1000
int main(void)
{
    int i, j, p, q, t, id[N], sz[N];
    for(i = 0; i < N; i++)
    {id[i] = i; sz[i] = 1;}
    while(scanf("%d %d", &p, &q) == 2)
    {
        for(i = p; i != id[i]; i = id[i]);    //寻找p对应的根节点
        for(j = q; j != id[j]; j = id[j]);    //根节点判断，i==id[i]
        if(i == j) continue;                  //已连通，进入下个循环
        if(sz[i] < sz[j])                     //i的节点数小于j
        {id[i] = j; sz[j] += sz[i];}          //把i连接到j上，j的节点数加上i的节点数
        else {id[j] = i; sz[i] += sz[j];}     //把j连接到i上，i的节点数加上j的节点数
        printf("output: %d %d\\n", p, q);
    }
    return 0;
}
对分路径压缩加权快速并集 weighted-quick-union-with-path-compression-by-halving

view plain
/* 连通性问题 Connectivity
* 对分路径压缩加权快速并集 weighted-quick-union-with-path-compression-by-halving
*
*/
#include <stdio.h>
#define N 1000
int main(void)
{
    int i, j, p, q, t, id[N], sz[N];
    for(i = 0; i < N; i++)
    {id[i] = i; sz[i] = 1;}
    while(scanf("%d %d", &p, &q) == 2)
    {
        for(i = p; i != id[i]; i = id[i])    //寻找p对应的根节点，根节点判断id[i]==i
            id[i] = id[id[i]];
        for(j = q; j != id[j]; j = id[j])
            id[j] = id[id[j]];
        if(i == j) continue;                  //已连通，进入下个循环
        if(sz[i] < sz[j])                     //i的节点数小于j
        {id[i] = j; sz[j] += sz[i];}          //把i连接到j上，j的节点数加上i的节点数
        else {id[j] = i; sz[i] += sz[j];}     //把j连接到i上，i的节点数加上j的节点数
        printf("output: %d %d\\n", p, q);
    }
    return 0;
}

Xushine

484