verify/Graph_cycle_detection_1.test.cpp

View this file on GitHub
Last update: 2025-01-11 19:27:04+09:00
Problem: https://judge.yosupo.jp/problem/cycle_detection

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/cycle_detection"
#include "../Utility/template.hpp"
#include "../Graph/cycle_detection.hpp"

int main() {
    int n, m;
    cin >> n >> m;
    cycle_detection<true> cyc(n);
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        cyc.add_edge(u, v);
    }
    auto [vs, es] = cyc.run();
    if (vs.empty()) {
        cout << -1 << endl;
    } else {
        cout << vs.size() << endl;
        // cout << vs << endl;
        for (int id : es) {
            cout << id << endl;
        }
    }
}

#line 1 "verify/Graph_cycle_detection_1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cycle_detection"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Graph/cycle_detection.hpp"
template <bool directed> struct cycle_detection {
    int n, ec;
    vector<vector<pair<int, int>>> g;
    cycle_detection(int n) : n(n), ec(0), g(n) {}

    void add_edge(int u, int v) {
        g[u].emplace_back(v, ec);
        if (directed == false) g[v].emplace_back(u, ec);
        ec++;
    }

    pair<vector<int>, vector<int>> run(int vertex = -1) {
        vector<bool> in(n, false);
        vector<bool> out(n, false);
        vector<int> vs;
        vector<int> es;
        const int fin = INT_MAX;
        auto dfs = [&](auto f, int v, int p) -> int {
            bool prev_edge = false;
            in[v] = true;

            for (auto [to, id] : g[v]) {
                if (to == p) {
                    if (directed == false) {
                        if (prev_edge == false) {
                            prev_edge = true;
                            continue;
                        } else {
                            vs.push_back(v);
                            es.push_back(id);
                            out[v] = true;
                            return to;
                        }
                    }
                }

                if (in[to] == true && out[to] == false) {
                    vs.push_back(v);
                    es.push_back(id);
                    out[v] = true;
                    return (v == to ? fin : to);
                }

                if (in[to] == false) {
                    int root = f(f, to, v);
                    if (root != -1 && root != fin) {
                        vs.push_back(v);
                        es.push_back(id);
                        out[v] = true;
                        return (v == root ? fin : root);
                    } else if (root == fin) {
                        out[v] = true;
                        return fin;
                    }
                }
            }
            out[v] = true;
            return -1;
        };

        int s = 0, t = n;
        if (vertex != -1) s = vertex, t = vertex + 1;

        for (int i = s; i < t; i++) {
            if (in[i] == false) {
                dfs(dfs, i, -1);
                if (vs.empty() == false) {
                    reverse(vs.begin(), vs.end());
                    reverse(es.begin(), es.end());
                    return make_pair(vs, es);
                }
            }
        }
        return make_pair(vs, es);
    }
};
/*
@brief cycle_detection
@docs doc/cycle_detection.md
*/
#line 4 "verify/Graph_cycle_detection_1.test.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    cycle_detection<true> cyc(n);
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        cyc.add_edge(u, v);
    }
    auto [vs, es] = cyc.run();
    if (vs.empty()) {
        cout << -1 << endl;
    } else {
        cout << vs.size() << endl;
        // cout << vs << endl;
        for (int id : es) {
            cout << id << endl;
        }
    }
}