結果

問題 No.1254 補強への架け橋
ユーザー tokusakurai
提出日時 2021-03-20 12:08:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 2,641 bytes
コンパイル時間 2,203 ms
コンパイル使用メモリ 205,076 KB
最終ジャッジ日時 2025-01-19 20:11:14
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 123
権限があれば一括ダウンロードができます

ソースコード

diff # 

//無向グラフでの基本的なDFS
//計算量 パス検出・閉路検出:O(E+V)

//verified with
//https://yukicoder.me/problems/no/1254

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

struct io_setup{
    io_setup(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout << fixed << setprecision(15);
    }
} io_setup;

template<bool directed = false>
struct Graph{
    struct edge{
        int to, id;
        edge(int to, int id) : to(to), id(id) {}
    };

    vector<vector<edge>> es;
    vector<int> used;
    const int n;
    int m;

    Graph(int n) : es(n), used(n), n(n), m(0) {}

    void add_edge(int from, int to){
        es[from].emplace_back(to, m);
        if(!directed) es[to].emplace_back(from, m);
        m++;
    }

    vector<int> ret_path;

    bool detect_path(int now, int t, bool use_id = false){
        used[now] = true;
        if(now == t){
            if(!use_id) ret_path.emplace_back(now);
            return true;
        }
        for(auto &e : es[now]){
            if(used[e.to]) continue;
            if(detect_path(e.to, t, use_id)){
                ret_path.emplace_back(use_id? e.id : now);
                return true;
            }
        }
        return false;
    }

    vector<int> find_path(int s, int t, bool use_id = false){
        ret_path.clear(), fill(begin(used), end(used), 0);
        detect_path(s, t, use_id);
        reverse(begin(ret_path), end(ret_path));
        return ret_path;
    }

    vector<int> ret_cycle;

    int detect_cycle(int now, int pre = -1, bool use_id = false){
        if(used[now]++) return 1;
        for(auto &e: es[now]){
            if(e.id == pre) continue;
            int k = detect_cycle(e.to, e.id, use_id);
            if(k == 2) return 2;
            if(k == 1){
                ret_cycle.emplace_back(use_id? e.id : now);
                return used[now];
            }
        }
        return 0;
    }

    vector<int> find_cycle(bool use_id = false){
        ret_cycle.clear(), fill(begin(used), end(used), 0);
        for(int i = 0; i < n; i++){
            if(used[i]) continue;
            detect_cycle(i, -1, use_id);
            if(!ret_cycle.empty()){
                reverse(begin(ret_cycle), end(ret_cycle));
                return ret_cycle;
            }
        }
        return {};
    }
};

int main(){
    int V; cin >> V;

    Graph G(V);

    for(int i = 0; i < V; i++){
        int u, v; cin >> u >> v; u--, v--;
        G.add_edge(u, v);
    }
    
    vector<int> cycle = G.find_cycle(true);

    cout << cycle.size() << '\n';
    for(auto &e: cycle) cout << e+1 << ' ';
    cout << '\n';
}
0