algorithm - Disjoint Setsを使用して無向グラフでサイクルを検出する方法は?

Question

アルゴリズム:

For each edge (u, v) in the Adjacency list:
If u and v do not belong to the same set:
   Union(u, v)
else:
  return true // cycle detected
return false

グラフ:

(1)------(2)

隣接リスト:

[1] -> [2]

[2] -> [1]

素集合:

{{1}、{2}}

反復 1 :

エッジ e = (1, 2)

ユニオン(1, 2)

素集合 = {{1, 2}}

反復 2 :

エッジ e = (2, 1)

2 と 1 の両方が同じセットに属しているため、アルゴリズムはサイクルを検出します。グラフにサイクルが含まれていないことは明らかです。

このアルゴリズムは、有向グラフに対して問題なく機能します。この分析を手伝ってください。