E. Directing Edges

Codeforces Round #656 (Div. 3)

https://codeforces.com/contest/1385/problem/E

問題

頂点辺のグラフが与えられる。
ここで、与えられる辺は、有向辺または無向辺のどちらかである。
無向辺に向きを付けることで、DAGを構成できるかどうか判定せよ。
判定できる場合は、構成したDAGの辺を出力しなさい。

解法

まず、元のグラフから無向辺を全て取り除いた有向グラフを生成します。
次に、をトポロジカルソートします。トポロジカルソート出来る条件は、DAGであることなので、もし失敗したらにはサイクルが存在しますから無向辺の向き付けをどんなに頑張ってもDAGを構成することは出来ません。
逆にトポロジカルソートが成功した場合は、必ず構成できます。この事実は下の図を見れば直感的に理解できると思います。

コード

https://codeforces.com/contest/1385/submission/95461303

using P = pair<int, int>;
vector<vector<int>> G;

vector<int> color;//0:未訪問, 1:保留, 2:決定済み
vector<int> res;
bool cycle = false;

void dfs(int v) {
    if (color[v] == 1) cycle = true;
    if (color[v] == 2 || cycle) return;

    //訪問したが頂点集合に加えられていないためステータスを保留とする
    color[v] = 1;

    for (auto nv : G[v]) {
        dfs(nv);
    }

    //帰りがけに頂点を加え、決定済みとする
    color[v] = 2;
    res.push_back(v);
}


void solve(){
    int n, m;
    cin >> n >> m;

    vector<P> ans;

    vector<P> E; //無向辺
    G.assign(n, vector<int>());

    rep(i, m) {
        int typ, a, b;
        cin >> typ >> a >> b;
        a--; b--;
        if (typ == 1) {
            G[a].push_back(b);
            ans.push_back(P{ a, b });
        }
        else {
            E.push_back(P{ a, b });
            E.push_back(P{ b, a });
        }
    }

    //有向グラフGをトポロジカルソート
    color.assign(n, 0);
    res = vector<int>();
    cycle = false;
    rep(i, n) {
        dfs(i);
    }
    reverse(all(res));

    if (cycle) {
        cout << "NO" << endl;
        return;
    }


    //頂点をトポロジカルソートしたときの順番
    map<int, int> ord;
    rep(i, n) ord[res[i]] = i;


    //後ろから前に向かって辺を向き付け
    for (auto e : E) {
        if (ord[e.first] < ord[e.second]) ans.push_back(P{ e.first, e.second });
    }

    //答えを出力
    cout << "YES" << endl;
    for (auto p : ans) cout << p.first + 1 << " " << p.second + 1 << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}