Implementation (Part 1)
Coddyの「クラスカル法 - グラフアルゴリズム」コースのレッスン 5/9。
まずは、サイクル検出エンジンであるUnion-Findから始めましょう。
チャレンジ
中級クラスカル法の閉路判定は、Union-Find（素集合データ構造）に依存しています。まずは、これを利用して連結成分の数をカウントするプログラムを作成しましょう。
n とフラットな edges 配列（[u, v, w, ...] の3つ組、無向グラフ、ここでは重み w は無視します）を引数に取り、Union-Find を用いて計算された連結成分の数を返す countSets という名前の関数を作成してください。
例えば、4つの頂点とエッジ [0,1,5, 2,3,5] がある場合、連結成分は {0,1} と {2,3} の2つになります。
自分で試してみよう
#include <stdlib.h>
int countSets(int n, int* edges, int edges_size) {
// ここにコードを記述してください
return 0;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
クラスカル法 - グラフアルゴリズムのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity