2019-09-29

AtCoder ABC 142 F - Pure (青色, 600 点)

AtCoder AtCoder600点 ABC-F グラフ応用的な探索サイクル DFS BFS 最短路問題考察テク:最大値や最小値に着目する復元青色diff サイクル検出【問題集】DFS・BFSのステップアップ

色んな方法がありそう。

問題へのリンク

問題概要

頂点数 $N$ 、辺数 $M$ の単純な有向グラフが与えられる。なお各有向辺の向きをなくして得られる無向グラフも単純であるとする (有向辺 (u, v) があったら辺 (v, u) はない)。

このグラフの有向サイクルであって、有向サイクル上のどの隣接しない二頂点間にも辺 (弦とよぶことにする) がないものが存在するかどうかを判定し、存在するならば一つ示せ。

制約

$1 \le N \le 1000$
$0 \le M \le 2000$

解法 1: 最短サイクルを求める

まず

有向サイクルを持たないならば問答無用で答えは -1
有向サイクルを持つならば、弦があったとしても下図のように弦を含むよりサイズの小さな有向サイクルを得ることができて (弦によってサイクルを二つに分けることができて、そのどちらかは向きが整合する)、この操作を繰り返すといつかは弦を持たない有向サイクルに収束する

ということを観察しておく。つまり有向サイクルがあるならば、とくに弦をもたない有向サイクルもあることがいえる。

このことからとくに

長さが最小の有向サイクルを求めると、それは弦をもたない

ということもわかる。最短サイクルは

各辺 (u, v) に対し、v を始点とした BFS を行う
BFS によって得られた最短の v-u パスに辺 (u, v) を付け加えたものが最短サイクルの候補である

という探索を各辺に対して行うことで得ることができる。実装上は各頂点 v を始点とした BFS を行えば良い。計算量は $O(N(N+M))$ となる。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// グラフ
using Graph = vector<vector<int> >;

int main() {
    int N, M; cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
    }

    int shortest = N+1;
    vector<int> res;
    for (int s = 0; s < N; ++s) {
        vector<int> dist(N, -1);
        vector<int> prev(N, -1);
        queue<int> que;
        que.push(s); dist[s] = 0;
        while (!que.empty()) {
            auto v = que.front(); que.pop();
            for (auto nv : G[v]) {
                if (dist[nv] == -1) {
                    dist[nv] = dist[v] + 1;
                    prev[nv] = v;
                    que.push(nv);
                }
            }
        }
        for (int t = 0; t < N; ++t) {
            if (t == s || dist[t] == -1) continue;
            for (auto nt : G[t]) {
                if (nt == s) {
                    vector<int> tmp({s});
                    int cur = t;
                    while (cur != s) tmp.push_back(cur), cur = prev[cur];
                    if (shortest > tmp.size()) {
                        shortest = tmp.size();
                        res = tmp;
                    }
                }
            }
        }
    }

    if (shortest == N+1) cout << -1 << endl;
    else {
        cout << res.size() << endl;
        for (auto v : res) cout << v+1 << endl;
    }
}

解法 2: 実際に弦で縮約を繰り返す

最後に、

有向サイクルを一つ求める
「弦」を見つけて、サイズの小さな有向サイクルを獲得する

という操作を実際に行う方法もある。有向サイクルを一つ見つけるのは、それだけなら実は $O(N + M)$ で実施することもできる。以下の記事に書いた。

qiita.com

これによって有向サイクルを一つ求めて、弦がなくなるまでサイズを小さくなることを繰り返しても通った。サイズを小さくする処理は $O(N + M)$ でできて最悪 $O(N)$ 回で収束するので計算量は $O(N(N+M))$ となる。

<feff>#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// グラフ
using Graph = vector<vector<int> >;
 
// 探索
vector<bool> seen, finished;
 
// サイクル復元のための情報
int pos = -1; // サイクル中に含まれる頂点 pos
vector<int> hist; // 訪問履歴
 
void dfs(const Graph &G, int v) {
    seen[v] = true;
    hist.push_back(v);
    for (auto nv : G[v]) {
        // 完全終了した頂点はスルー
        if (finished[nv]) continue;
 
        // サイクルを検出
        if (seen[nv] && !finished[nv]) {
            pos = nv;
            return;
        }
 
        // 再帰的に探索
        dfs(G, nv);
 
        // サイクル検出したならば真っ直ぐに抜けていく
        if (pos != -1) return;
    }
    hist.pop_back();
    finished[v] = true;
}

int main() {
    int N, M; cin >> N >> M;
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
    }

    // 探索
    seen.assign(N, false), finished.assign(N, false);
    pos = -1;
    for (int v = 0; v < N; ++v) {
        pos = -1;
        dfs(G, v);
        if (pos != -1) break;
    }

    // 有向サイクルなし
    if (pos == -1) {
        cout << -1 << endl;
        return 0;
    }

    // 有向サイクルを復元
    vector<int> cycle;
    while (!hist.empty()) {
        int t = hist.back();
        cycle.push_back(t);
        hist.pop_back();
        if (t == pos) break;
    }
    reverse(cycle.begin(), cycle.end());
    
    // サイクル中に「弦」があったら、小さくする
    while (true) {
        int from = -1, to = -1;
        vector<int> ord(N, -1);
        for (int i = 0; i < cycle.size(); ++i) ord[cycle[i]] = i;
        for (int i = 0; i < cycle.size(); ++i) {
            for (auto nv : G[cycle[i]]) {
                if (nv != cycle[(i+1)%cycle.size()] && ord[nv] != -1) {
                    from = i, to = ord[nv];
                }
            }
        }
        if (from == -1) break; // 弦がなくなって終了

        vector<int> ncycle;
        ncycle.push_back(cycle[from]);
        int id = to;
        while (id != from) {
            ncycle.push_back(cycle[id]);
            id = (id + 1) % cycle.size();
        }
        cycle = ncycle;
        
        //COUT(from); COUT(to); COUT(cycle);
    }
    
    cout << cycle.size() << endl;
    for (auto v : cycle) cout << v + 1 << endl;
}