C++で無向グラフを「長さ2以上のパスが存在しない有向グラフ」に変換する方法

この記事では、無向グラフを「どの有向パスの長さも1を超えない有向グラフ」に変換するC++プログラムについて詳しく解説します。

問題の概要

入力として無向グラフが与えられます。私たちの課題は、このグラフを有向グラフへ変換することです。ただし、変換後のグラフには長さが1より大きい(=2以上の)パスが一切存在してはいけないという制約があります。この条件を満たす変換が不可能な場合は -1 を出力します。

解法のカギ:二部グラフとの関係

この問題は、グラフが二部グラフ(bipartite graph)であるかどうかと深い関係があります。

グラフの頂点を2つの集合に分割でき、すべての辺が一方の集合からもう一方の集合へ向くように辺を張れば、どの頂点から出発しても1歩進むだけで行き止まりになるため、長さ2以上のパスは絶対に発生しません。

逆に、グラフが二部グラフでない(奇閉路を含む)場合、どのように辺の向きを決めても長さ2以上のパスが必ず生じるため、変換は不可能です。したがって、アルゴリズムは次の手順になります。

1. DFS(深さ優先探索)でグラフを2色に塗り分け、二部グラフかどうかを判定する。
2. 二部グラフでなければ -1 を出力して終了する。
3. 二部グラフであれば、「色1の頂点 → 色0の頂点」となるよう各辺の向きを揃えて出力する。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
#define N 100005
// グラフの隣接リスト
vector<int> gr[N];
// 各頂点の色を格納
int colour[N];
// 辺のリスト
vector<pair<int, int> > edges;
bool bip;
// 辺をグラフに追加する
void add_edge(int x, int y){
    gr[x].push_back(y);
    gr[y].push_back(x);
    edges.push_back(make_pair(x, y));
}
// グラフが二部グラフかどうかを判定する
void dfs(int x, int col){
    colour[x] = col;
    // 子頂点へ移動
    for (auto i : gr[x]) {
        if (colour[i] == -1)
            dfs(i, col ^ 1);
        // 隣接頂点同士が同じ色の場合
        else if (colour[i] == col)
            bip = false;
    }
}
// 有向グラフへの変換
void convert_directed(int n, int m){
    memset(colour, -1, sizeof colour);
    bip = true;
    // 二部グラフ判定を実行
    dfs(1, 1);
    if (!bip) {
        cout << -1;
        return;
    }
    // 二部グラフの場合は辺の向きを揃える
    for (int i = 0; i < m; i++) {
        if (colour[edges[i].first] == 0)
            swap(edges[i].first, edges[i].second);
        cout << edges[i].first << " " << edges[i].second << endl;
    }
}
int main(){
    int n = 4, m = 3;
    add_edge(1, 2);
    add_edge(1, 3);
    add_edge(1, 4);
    convert_directed(n, m);
    return 0;
}

出力結果

1 2
1 3
1 4

コードの解説

• add_edge関数: 隣接リストに両方向の辺を登録するとともに、後で向きを出力できるよう辺リスト(edges)にも記録します。
• dfs関数: 隣接する頂点を交互に色0と色1で塗り分けていくことで二部グラフ判定を行います。塗る予定の隣接頂点が現在と同じ色だった場合、そのグラフは二部グラフではないと判断し、フラグをfalseにします。
• convert_directed関数: 全頂点を未着色(-1)に初期化したうえでDFSを開始します。二部グラフでなければ -1 を出力して終了し、そうでなければ各辺について「始点の色が0なら両端を入れ替える」ことで、すべての辺を色1から色0へ向くように統一して出力します。

計算量

二部グラフ判定のDFSがO(N + M)、辺の向き決めがO(M)となるため、全体の計算量はO(N + M)(N:頂点数、M:辺数)です。大規模なグラフに対しても効率的に動作します。