ICPC 2019 Asia Yokohama Regional I One-Way Conveyors

問題ページ

問題概要

頂点 辺のグラフが与えられる． 個の経路 が到達可能なように，辺の向きを定めることが可能か？可能な場合どのような向きにするかも出力せよ．

解法

グラフに対して二重辺連結成分分解を行う．二重辺連結成分については，一つのサイクルになるように向きを定めれば全ての頂点間を自由に行き来できる．橋についてうまく向きを定めることで，全ての経路が到達可能か？と言う問題になったので，あとは木について解けばよい．

に関してどのような向きを定めるべきか考える． とすると から を上向きの辺， から を下向きの辺とすればよい．木上のimosの要領であるパスを上向き/下向きと定めることができる．したがって，木に対してこの問題が解けた．

あとは二重辺連結成分の全ての頂点を行き来できるような，辺の向きの定め方がわかればよい．dfsを行い，後退辺(dfsで通らなかった辺)を子から親への向きにすればよい．橋が存在しないことからdfs木の全ての辺に対して，交差するような祖先へ戻る辺が存在する．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long int;  
using PII = pair<ll,ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
  
set<PII> st;  
vector<PII> ans;  
struct twoEdgeComponents {  
    int n;  
    vector<vector<int>> g;  
    vector<int> cmp;  
    vector<vector<int>> each_bcc;  
    vector<pair<int,int>> bridge;  
    vector<int> order;  
    vector<bool> inS;  
    stack<int> roots, S;  
  
    void dfs(int cur, int prev, int &k) {  
        order[cur] = ++k;  
        S.push(cur); inS[cur] = true;  
        roots.push(cur);  
  
        for(auto to: g[cur]) {  
            if(order[to]==0) dfs(to, cur, k);  
            else if(to != prev && inS[to]) {  
                while(order[roots.top()] > order[to]) roots.pop();  
            }  
        }  
  
        if(cur == roots.top()) {  
            if(prev!=-1) bridge.push_back({prev, cur});  
            vector<int> bcc;  
            while(1) {  
                int node = S.top(); S.pop(); inS[node] = false;  
                bcc.push_back(node);  
                if(node == cur) break;  
            }  
            each_bcc.push_back(bcc);  
            roots.pop();  
        }  
    }  
  
    twoEdgeComponents() {}  
    twoEdgeComponents(int n): n(n), g(n) {}  
  
    void add_edge(int p, int q) {  
        g[p].push_back(q);  
        g[q].push_back(p);  
    }  
    void bcc() {  
        order.assign(n, 0);  
        inS.assign(n, false);  
        cmp.assign(n, -1);  
        int k = 0;  
        for(int i=0; i<n; ++i) {  
            if(order[i] == 0) {  
                dfs(i, -1, k);  
            }  
        }  
        REP(i, (int)each_bcc.size()) {  
            for(auto j: each_bcc[i]) cmp[j] = i;  
        }  
    }  
    using P = pair<ll,PII>;  
    vector<vector<P>> getbcc() {  
        vector<vector<P>> h(each_bcc.size());  
        for(auto i: bridge) {  
            int a = cmp[i.first], b = cmp[i.second];  
            h[a].push_back({b, i});  
            h[b].push_back({a, {i.second, i.first}});  
        }  
        return h;  
    }  
  
    vector<ll> dep;  
    void func(ll v, ll p) {  
        for(auto to: g[v]) {  
            if(cmp[v] != cmp[to]) continue;  
            if(to == p) continue;  
            if(dep[to] == -1) {  
                ans.push_back({v, to});  
                st.insert({min(v, (ll)to), max(v, (ll)to)});  
                dep[to] = dep[v] + 1;  
                func(to, v);  
            }  
        }  
    }  
};  
  
struct LCA {  
    const int n = 0;  
    const int log2_n = 0;  
    vector<vector<int>> g;  
    vector<vector<int>> par;  
    vector<int> dep;  
  
    void dfs(int v, int p, int d) {  
        par[0][v] = p;  
        dep[v] = d;  
        for(auto to: g[v]) {  
            if(to == p) continue;  
            dfs(to, v, d+1);  
        }  
    }  
  
    LCA() {}  
    LCA(int n) : n(n), log2_n(log2(n)+1), g(n),  
        par(log2_n, vector<int>(n)), dep(n) {}  
  
    void add_edge(int u, int v) {  
        g[u].push_back(v);  
        g[v].push_back(u);  
    }  
  
    void build(ll root=0) {  
        dfs(root, -1, 0);  
        for(int i=0; i+1 < log2_n; ++i) {  
            for(int j = 0; j < n; ++j) {  
                if(par[i][j] < 0) par[i+1][j] = -1;  
                else par[i+1][j] = par[i][par[i][j]];  
            }  
        }  
    }  
  
    int get(int u, int v) {  
        if(dep[u] > dep[v]) swap(u, v);  
        REP(i, log2_n) {  
            if((dep[v] - dep[u]) >> i & 1) {  
                v = par[i][v];  
            }  
        }  
        if(u == v) return u;  
        for(int i=log2_n-1; i>=0; --i) {  
            if(par[i][u] != par[i][v]) {  
                u = par[i][u];  
                v = par[i][v];  
            }  
        }  
        return par[0][u];  
    }  
};  
  
signed main() {  
    ll n, m;  
    cin >> n >> m;  
    twoEdgeComponents graph(n);  
    vector<ll> a(m), b(m);  
    REP(i, m) {  
        cin >> a[i] >> b[i];  
        a[i]--, b[i]--;  
        graph.add_edge(a[i], b[i]);  
    }  
    graph.bcc();  
  
    // サイクルの部分  
    graph.dep.assign(n, -1);  
    REP(i, graph.each_bcc.size()) {  
        graph.dep[graph.each_bcc[i][0]] = 0;  
        graph.func(graph.each_bcc[i][0], -1);  
    }  
    REP(i, m) {  
        PII p({min(a[i], b[i]), max(a[i], b[i])});  
        if(graph.cmp[a[i]] == graph.cmp[b[i]] && st.find(p) == st.end()) {  
            if(graph.dep[a[i]] < graph.dep[b[i]]) {  
                ans.push_back({b[i], a[i]});  
            } else {  
                ans.push_back({a[i], b[i]});  
            }  
            st.insert(p);  
        }  
    }  
  
    // LCAを求めるための準備  
    auto g = graph.getbcc();  
    LCA tree(graph.each_bcc.size());  
    REP(i, g.size()) {  
        for(auto j: g[i]) {  
            if(i < j.first) tree.add_edge(i, j.first);  
        }  
    }  
    tree.build();  
  
    // imosで上向き/下向きの辺を定める  
    vector<ll> up(g.size()), down(g.size());  
    ll q;  
    cin >> q;  
    vector<ll> u(q), v(q);  
    REP(i, q) {  
        cin >> u[i] >> v[i];  
        u[i]--, v[i]--;  
  
        if(graph.cmp[u[i]] == graph.cmp[v[i]]) continue;  
        u[i] = graph.cmp[u[i]];  
        v[i] = graph.cmp[v[i]];  
        ll lca = tree.get(u[i], v[i]);  
        up[u[i]]++;  
        up[lca]--;  
        down[v[i]]++;  
        down[lca]--;  
    }  
  
    function<void(ll,ll)> dfs = [&](ll v, ll p) {  
        for(auto to: g[v]) {  
            if(to.first == p) continue;  
            dfs(to.first, v);  
  
            // imos用の累積和  
            down[v] += down[to.first];  
            up[v] += up[to.first];  
            // 両方の向きが必要  
            if(down[to.first] > 0 && up[to.first] > 0) {  
                cout << "No" << endl;  
                exit(0);  
            }   
            // 下向きの辺  
            else if(down[to.first] > 0) {  
                ans.push_back({to.second.first, to.second.second});  
            }   
            // 上向きの辺  
            else {  
                ans.push_back({to.second.second, to.second.first});  
            }  
        }  
    };  
    dfs(0, -1);  
  
    cout << "Yes" << endl;  
    for(auto p: ans) cout << p.first+1 << " " << p.second+1 << endl;  
  
    return 0;  
}