0

我正在使用联合查找算法来查找无向图的所有连通分量。由于某些未知原因，它给出了错误的答案。我给出的输入图是连接的，但它为该图输出了 2 个不同的标签。

如果有人能解释这个异常，我会很高兴。是否存在一些特殊的无向图，Union-Fid 可能不起作用？

** 图表有点大，所以我添加了一张图片以提高图表的可读性。无法修剪图表，否则问题的本质将消失。**

这里，p 和 rk 分别是父级和排名。

代码

联合函数

 void union_find(int x, int y, int *p, int *rk)
{
    int px = find(x, p);
    int py = find(y, p);
    if(px != py)
    {
        if(rk[px] < rk[py])
        {
            p[px] = py;
        }
        else
        {
            p[py] = px;
            if(rk[px] == rk[py]) rk[px]++;
        }
    }
}

查找功能 

int find(int x , int *p)
{
    return (p[x] == x) ? x : p[x] = find(p[x], p);
}

样本输入

37 51
4 5
4 10
5 7
5 8
5 9
6 7
6 16
7 8
7 15
8 9
8 10
10 11
10 14
11 12
12 21
13 14
13 32
14 15
14 22
15 16
15 22
16 17
17 22
17 19
19 24
19 27
20 30
20 32
21 31
22 23
22 36
23 24
23 36
24 25
25 26
26 36
26 27
27 28
27 29
27 32
27 37
28 29
29 30
31 32
32 33
32 35
33 34
33 35
34 35
35 36
36 37

图表照片

请注意，我没有考虑节点 1、2、3 和 18 及其边缘。

无向图

4

0 回答 0