アプリをダウンロード
フォルダーを選び、編集前に関連ファイルを読むようアシスタントに依頼します。作業の目的と変更範囲を明確にしてください。
ワークフロー
コーディングのワークフロー · 有向グラフの強連結成分
03
ワークフロー
頂点数が最大64の有向グラフを強連結成分に分割します。閉路、孤立頂点、空の入力を試し、隣接集合を変更せずに不正な集合要素を拒否します。
プロジェクトフォルダーを開く
対応するエンドポイントを選択します。利用できるツールや回答品質は、設定したモデルとサーバーに依存します。
モデルを接続してテスト
変更内容とコマンド出力を確認します。結果を採用する前にプロジェクトの検証を実行してください。生成コードが自動的にテスト済みになるわけではありません。
変更を確認しテストを実行
実際の動作を期待する結果と比較します。検証に失敗した場合は、次の変更を加える前に原因を調べてください。
有向グラフの強連結成分
ワークフロー
def strong_components(graph):
if type(graph) is not list or len(graph) > 64:
raise ValueError("scc.graph")
n = len(graph)
if any(type(row) is not set or any(type(v) is not int or not 0 <= v < n for v in row) for row in graph):
raise ValueError("scc.edge")
seen, order = set(), []
for start in range(n):
if start in seen:
continue
seen.add(start)
stack = [(start, iter(sorted(graph[start])))]
while stack:
node, edges = stack[-1]
target = next(edges, None)
if target is None:
order.append(node)
stack.pop()
elif target not in seen:
seen.add(target)
stack.append((target, iter(sorted(graph[target]))))
reverse = [set() for _ in graph]
for node, edges in enumerate(graph):
for target in edges:
reverse[target].add(node)
seen, result = set(), []
for start in reversed(order):
if start in seen:
continue
group, pending = [], [start]
seen.add(start)
while pending:
node = pending.pop()
group.append(node)
for target in reverse[node]-seen:
seen.add(target)
pending.append(target)
result.append(sorted(group))
return sorted(result)
適用前に確認. 変更内容とコマンド出力を確認します。結果を採用する前にプロジェクトの検証を実行してください。生成コードが自動的にテスト済みになるわけではありません。