橋と関節点
グラフを分断する辺とノードを見つけます
「橋と関節点」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
グラフの脆い箇所
無向グラフには重要な部分があります。それらを取り除くとグラフが分断されます。そこを見つけることで、弱い接続部分が明らかになります。
橋とは
橋とは、取り除くと連結成分の数が増える辺です。2つの領域を結ぶ唯一の経路になっています。
関節点とは
関節点とは、取り除くとグラフが非連結になるノードです。ネットワークにとって、単一障害点にあたります。
DFS木をもう一度見る
どちらも1回のDFSで動作し、発見時刻と low 値を管理します。Tarjanのアルゴリズムとよく似ていますが、無向グラフを対象にします。
disc = [-1] * n
low = [-1] * nlowは最も早く到達できる発見番号
ノードのlowは、そのDFS部分木から到達できる最小の発見番号です。場合によっては、1本の後退辺を上へたどって到達します。
入った時点で初期化する
DFSでノードに入ったら、現在のタイマーの値をdisc と lowに記録し、隣接ノードへ進みます。
disc[u] = low[u] = timer
timer += 1橋の条件
子 v へ再帰した後、low[v] > disc[u] なら、u より先へ抜ける後退辺はありません。したがって辺 u-v は橋です。
if low[v] > disc[u]:
bridges.append((u, v))関節点の条件
根でない u は、子 v が low[v] >= disc[u] を満たすとき関節点です。v の部分木は u を迂回できません。
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)根の場合の特別扱い
DFSの根が関節点になるのは、DFS木で2つ以上の子を持つ場合だけです。そのため、子の数を数えます。
if parent[u] == -1 and children > 1:
art.add(u)親への辺をスキップする
後退辺から low を更新するときは、親へ向かう辺を逆にたどらないでください。そうしないと橋を誤判定します。
if v != parent[u]:
low[u] = min(low[u], disc[v])1回の探索で両方を求める
1回のDFSで、すべての橋と関節点を同時にO(V + E)で見つけられます。追加の探索は必要ありません。
理解度チェック
u から子 v へ再帰した後、low[v] > disc[u] でした。何を見つけましたか？
まとめ: 重要な辺とノード
disc と low を使った1回のDFSですべてを見つけられます。low[v] > disc[u] は橋を、low[v] >= disc[u] は関節点を示します。🌉
よくある質問
「橋と関節点」レッスンは無料ですか？
はい。「橋と関節点」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「橋と関節点」で何を学びますか？
グラフを分断する辺とノードを見つけます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「橋と関節点」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。