2-SAT問題の効率的解法と実装テクニック
制約充足問題のモデリング
論理変数の組み合わせで矛盾しない割り当てを求める問題において、各制約が「Aを選択するならばBは不可」のような2項条件に限定される場合、2-SATアルゴリズムが有効です。この手法は、論理式を有向グラフとして表現し、強連結成分(SCC)の解析を通じて解の存在を判定します。
グラフ構築のポイント
各変数xについて、2つのノードを定義します：
...
6月21日 18:03 投稿
グラフアルゴリズムの実装と応用
グラフの冗長接続検出
無向グラフにおいて、ツリー構造を維持しながら冗長な接続を特定する方法について説明します。
Union-Findによる冗長接続の検出
#include <iostream>
#include <vector>
using namespace std;
class UnionFind {
private:
vector<int> parent;
public:
UnionFind(int n) : parent(n + 1) {
for (int i = 0; i &l ...
6月19日 19:16 投稿
コーススケジュールII - トポロジカルソート - DFS・BFSによる解法
問題概要
0からnumCourses-1までの整数で表される複数のコースが存在します。配列prerequisitesの各要素prerequisites[i] = [ai, bi]は、コースaiを受講する前にbiを完了する必要があることを示します。
すべてのコースを受講可能な順序を返してください。複数の有効な順序が存在する場合は、そのいずれかを返します。不可能な場合は空配列を返します。
例1
入力: numCou ...
5月30日 02:57 投稿