ユニオン検索アルゴリズムを使用して、無向グラフのすべての接続コンポーネントを検索しています。いくつかの不明な理由により、間違った答えが返されます。私が与える入力グラフは接続されていますが、そのグラフには 2 つの異なるラベルが出力されます。
誰かがこの異常を説明できれば幸いです。Union-Find が機能しない特別な無向グラフはありますか?
** グラフが少し大きいので、グラフを見やすくするために画像を追加しました。グラフをトリミングできませんでした。そうしないと、質問の本質が消えてしまいます。**
ここで、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 とそのエッジは考慮していないことに注意してください。
