Yosupo Library Checker - Cycle Detection (Undirected)

これも Yosupo Judge の問題名でタイトル検索しても出てくるように。

• 問題へのリンク

問題概要

頂点 辺の無向グラフが与えられる。 番目の辺は頂点 を結ぶ。単純グラフとは限らない。

与えられたグラフにサイクルが含まれるならば、辺素かつ頂点素なサイクルを 1 つ見つけて報告せよ (存在しない場合は -1 を出力)。

具体的には、サイクルに含まれる辺番号と頂点番号を順番に出力せよ。サイクルが複数含まれるならばどれを出力してもよい。

なお、自己ループも長さ 1 のサイクルとみなす。

制約

• 
• 

解法

次の点に注意を要する。

• 多重辺でない辺 があるときに、その辺を二度使う はサイクルではない
• 一方、多重辺 があるときは、それらを一度ずつ使う はサイクルである

今回は、後者については、入力を受け取る時にあらかじめ検出してしまうこととした。

それにより、サイクル検出アルゴリズムを適用する時点では、多重辺は含まないものとして扱うことができる。サイクル検出アルゴリズムについては、次の記事に詳しく書いた。

drken1215.hatenablog.com

コード

計算量は、サイクル検出アルゴリズムを適用する本質的部分は だが、多重辺の検出のために map 型を用いているため、 となっている。

#include <bits/stdc++.h>
using namespace std;

// 辺を表す構造体
template<class T> struct Edge {
    int from, to;
    T val;
    Edge(int f = -1, int t = -1, T v = -1) : from(f), to(t), val(v) {}
};

// グラフを表す型
template<class T> using Graph = vector<vector<Edge<T>>>;

// サイクル検出ソルバー
template<class T> struct CycleDetection {
    // 入力されたグラフ
    Graph<T> G;
    
    // 探索の様子
    vector<bool> seen, finished;
    vector<Edge<T>> history;
    
    // コンストラクタ
    CycleDetection() { }
    CycleDetection(const Graph<T> &graph) { init(graph); }
    void init(const Graph<T> &graph) {
        G = graph;
        seen.assign(G.size(), false);
        finished.assign(G.size(), false);
    }
    
    // サイクル検出
    // return the vertex where cycle is detected
    int dfs(int v, const Edge<T> &e, bool is_prohibit_reverse = true) {
        seen[v] = true;    // 行きがけ時に true になる
        history.push_back(e);    // 履歴を残す
        for (const Edge<T> &e2 : G[v]) {
            // 逆流を禁止する場合は逆流を禁止する
            if (is_prohibit_reverse && e2.to == e.from) continue;
            
            // 頂点 v2 がすでに探索済みの場合はスキップ
            if (finished[e2.to]) continue;

            // サイクルが検出された
            if (seen[e2.to] && !finished[e2.to]) {
                history.push_back(e2);
                return e2.to;
            }

            // 頂点 v2 を再帰的に探索する
            int pos = dfs(e2.to, e2, is_prohibit_reverse);
            if (pos != -1) return pos;
        }
        finished[v] = true;    // 帰りがけ時に true になる
        history.pop_back();    // 探索が完全に終了した頂点 (赤色) は履歴から除去する
        return -1;
    }
    
    // 履歴からサイクルのみを抽出する関数 (pos：サイクルを検出した頂点)
    vector<Edge<T>> reconstruct(int pos) {
        vector<Edge<T>> cycle;
        
        // 履歴を遡ってサイクルを形作る
        while (!history.empty()) {
            const Edge<T> &e = history.back();
            cycle.push_back(e);
            history.pop_back();
            if (e.from == pos) break;
        }
        
        // サイクルの向きを正順にする
        reverse(cycle.begin(), cycle.end());
        return cycle;
    }
    
    // サイクルを返す関数 (is_prohibit_reverse は逆流を許さないかどうか)
    vector<Edge<T>> detect(bool is_prohibit_reverse = true) {
        int pos = -1;
        for (int v = 0; v < (int)G.size() && pos == -1; ++v) {
            if (seen[v]) continue;
            history.clear();
            pos = dfs(v, Edge<T>(), is_prohibit_reverse);
            if (pos != -1) return reconstruct(pos);
        }
        return vector<Edge<T>>();
    }
};

int main() {
    // 有向グラフの受け取り, 多重辺と自己ループは予め除去しておく
    int N, M;
    cin >> N >> M;
    Graph<int> G(N);
    map<pair<int,int>, int> edges;
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        
        // 多重辺
        if (u > v) swap(u, v);
        if (edges.count({u, v})) {
            cout << 2 << endl;
            cout << u << " " << v << endl;
            cout << edges[{u, v}] << " " << i << endl;
            return 0;
        }
        
        G[u].push_back(Edge(u, v, i));
        G[v].push_back(Edge(v, u, i));
        edges[{u, v}] = i;
    }
    
    // cycle detection
    CycleDetection<int> cd(G);
    const vector<Edge<int>> &res = cd.detect(true);
    
    // 出力
    if (res.empty()) cout << -1 << endl;
    else {
        cout << res.size() << endl;
        for (const Edge<int> &e : res) cout << e.from << " ";
        cout << endl;
        for (const Edge<int> &e : res) cout << e.val << " ";
        cout << endl;
    }
}