AtCoder Beginner Contest 142 F - Pure

問題文: F - Pure

Writer 解説: https://img.atcoder.jp/abc142/editorial.pdf

問題概要

$ N (\leq 1000)$ 頂点 $ M (\leq 2000)$ 辺の有向グラフG が与えられる．

すべての頂点の入次数が 1 ，出次数が 1 となるような G の部分誘導グラフを 1 つ答えよ．ただし，空グラフは含まない．

解法概要

図1: 問題の条件を満たす部分誘導グラフの例

「すべての頂点の入次数が 1 ，出次数が 1 となるような G の部分誘導グラフ」というのは，図1のような部分誘導グラフ $ G^\prime$ を構成するすべての頂点が一つの閉路を作っており，分岐がないようなグラフである．

つまり，閉路が存在しないときは問題の条件を満たす部分誘導グラフは存在しない．

閉路を見つけるには， dfs をしながら先祖とつながっている頂点がないか探せばよい．同時に，dfs で辿ってきた頂点は保存しておき，見つけた閉路が条件を満たすかどうかの確認および条件を満たすために行う閉路の縮約に用いる．なお今回は閉路を列挙していると時間が足りないしすべての閉路の情報が必要なわけではないので，閉路を 1 つ見つけたら探索をやめてよい．

さて，dfs で 1 つでも閉路を見つけたら，その閉路が問題の条件を満たすか確認する必要がある．閉路に使われる頂点同士をつなぐ辺だけを残した新しいグラフを作ったとき，図1のように条件を満たしていればよいが，図2のように閉路の中に余計な辺がある場合もある．図2の場合，部分誘導グラフに頂点 1〜6 をすべて含もうとすると 2 -> 6 のような閉路を作らない辺が入るので，頂点 1, 2, 6 からなる新しい閉路を作りたい．

図2: 問題の条件を満たさない部分誘導グラフの例

新しい部分誘導グラフを作るには，まず 2 -> 6のような閉路を作らない辺を検出する必要がある．これは dfs で閉路を探すときに閉路を作っている頂点とその順番を記録しておき，その情報を使うことで実現できる．すなわち，部分誘導グラフの中で閉路を作っている辺をチェックすれば，チェックされていない辺が閉路を作らない辺ということである．

閉路を作らない辺を見つけたら，今度はその辺 $ e$ を使ったより小さい閉路 を作る．これは元々の部分誘導グラフの閉路のうち，$ e$ の終点で始まり $ e$ の始点でで終わるような部分 (図2 では 6->1->2) を持ってきて，これと $ e$ を合わせればよい (図2 では 6->1->2->6) ．個人的には，dfs の地点で閉路に使われる頂点を deque に持っておくことでこの部分の実装が楽になった気がする (ソースコード中の deque<int> history)．

以降は，新しい閉路に含まれる頂点同士をつなぐ辺のみを残した新しい部分誘導グラフを作り，閉路を作らない辺を検出し，また新しい部分誘導グラフを作る……といったことを条件を満たすまで繰り返す．

dfs で閉路を見つけて以降に作る部分誘導グラフは常に閉路を持つし，新しい閉路を作るたびに頂点数は減っていく．そして，頂点数が2の閉路を持つグラフは常に問題の条件を満たす．このことから，前段落の繰り返しは必ず条件を満たして終了することができる．

元々のグラフは $ N (\leq 1000)$ 頂点 $ M (\leq 2000)$ 辺なので，閉路を全部列挙しようとするとかしない限り間に合う．

ソースコード

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

using Pii = pair<int, int>;

constexpr int N_MAX = 1123;

int n, m;
vector<int> graph[N_MAX];
vector<Pii> edges;
vector<bool> used(N_MAX, false), in_history(N_MAX, true);
deque<int> history;

inline void show_history() {
    int l = history.size();
    cout << l << endl;
    for(int i=0;i<l;++i) {
        cout << history[i]+1 << endl;
    }
}

inline bool check() {
    vector<int> indeg(N_MAX, 0), outdeg(N_MAX, 0);
    for(int i: history) {
        for(int j: graph[i]) {
            ++outdeg[i];
            ++indeg[j];
        }
    }

    for(int x: history) {
        if(outdeg[x] != 1 || indeg[x] != 1) return false;
    }
    return true;
}

inline bool dfs(int node) {
    used[node] = true;
    in_history[node] = true;
    history.push_back(node);
    for(int child: graph[node]) {
        if(in_history[child]) {
            while(history.front() != child) {
                in_history[history.front()] = false;
                history.pop_front();
            }
            return true;
        }
        if(dfs(child)) return true;
    }
    history.pop_back();
    in_history[node] = false;
    return false;
}

int main() {
    cin >> n >> m;
    int a, b;
    for(int i=0;i<m;++i){
        cin >> a >> b;
        --a; --b;
        graph[a].push_back(b);
        edges.emplace_back(a, b);
    }

    // 閉路探し (閉路がなければ終わり)
    {
        int i = 0;
        for(;i<n;++i) {
            if(used[i]) continue;
            in_history = vector<bool>(N_MAX, false);
            if(dfs(i)) break;
        }
        if(i == n) {
            cout << -1 << endl;
            return 0;
        }
    }

    // 閉路縮約
    while(!check()) {
        // いらないエッジを消す
        for(int i=0;i<n;++i) graph[i].clear();
        for(Pii e: edges) {
            if(in_history[e.first] && in_history[e.second]) {
                graph[e.first].push_back(e.second);
            }
        }

        // 閉路を作っている辺をチェックする
        vector<bool> selected[n];
        for(int i=0;i<n;++i) {
            selected[i].assign(graph[i].size(), false);
        }
        int n_history = history.size();
        for(int i=0;i<n_history;++i) {
            int a = history[i], b = history[(i+1)%n_history];
            for(int j=0;j<graph[a].size();++j) {
                if(graph[a][j] == b) {
                    selected[a][j] = true;
                }
            }
        }

        // 閉路を作っている辺以外の辺を見つける
        Pii e = {-1, -1};
        for(int i=0;i<n;++i) {
            for(int j=0;j<selected[i].size();++j) {
                if(selected[i][j] == 0) {
                    e.first = i;
                    e.second = graph[i][j];
                    break;
                }
            }
        }

        // いらないノードを消す
        if(e.first != -1) {
            while(history.front() != e.second) {
                history.push_back(history.front());
                history.pop_front();
            }
            while(history.back() != e.first) {
                in_history[history.back()] = false;
                history.pop_back();
            }
        }
    }

    show_history();
    return 0;
}

所感

前回の ABC ではレートを1500台まで戻すことができて，やっとスランプから脱出できたのではと思っています．

しかしこれは本番で解きたかった……．