kyopro_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub dyktr06/kyopro_library

:heavy_check_mark: test/library_checker/graph/cycle_detection.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/cycle_detection"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/graph/dijkstra.hpp"
#include "../../../lib/graph/scc.hpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<int> u(m), v(m);
    map<pair<int, int>, int> e;
    for(int i = 0; i < m; i++){
        cin >> u[i] >> v[i];
        e[{u[i], v[i]}] = i;
    }
    vector<vector<int>> G(n);
    SCC scc(n);
    vector<vector<array<long long, 2>>> G2(n);
    for(int i = 0; i < m; i++){
        scc.add_edge(u[i], v[i]);
        G2[u[i]].push_back({v[i], 1});
    }
    scc.build();
    vector<int> ans;
    for(auto &s : scc.get()){
        int sizs = s.size();
        if(sizs == 1) continue;
        auto [w1, e1] = shortest_path(G2, s[0], s[1]);
        auto [w2, e2] = shortest_path(G2, s[1], s[0]);
        for(auto [a, b] : e1){
            ans.push_back(e[{a, b}]);
        }
        for(auto [a, b] : e2){
            ans.push_back(e[{a, b}]);
        }
        break;
    }

    int siz = ans.size();
    if(siz == 0){
        cout << -1 << "\n";
        return 0;
    }
    cout << siz << "\n";
    for(int i = 0; i < siz; i++){
        cout << ans[i] << "\n";
    }
}
#line 1 "test/library_checker/graph/cycle_detection.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cycle_detection"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/graph/dijkstra.hpp"

/**
 * @brief Dijkstra's Algorithm (ダイクストラ法)
 * @docs docs/graph/dijkstra.md
 */

template <typename T>
vector<long long> dijkstra(const vector<vector<array<long long, 2>>> &G, T x){
    const long long INF = 0x1fffffffffffffff;
    vector<long long> cost((int) G.size(), INF);
    using P = pair<long long, long long>;
    priority_queue<P, vector<P>, greater<>> q;
    cost[x] = 0;
    q.emplace(0, x);

    while(q.size()){
        auto [c, at] = q.top();
        q.pop();
        if(c > cost[at]) continue;
        for(auto &[to, t] : G[at]){
            if(cost[to] > c + t){
                cost[to] = c + t;
                q.emplace(cost[to], to);
            }
        }
    }
    return cost;
}

pair<long long, vector<pair<int, int>>> shortest_path(const vector<vector<array<long long, 2>>> &G, int s, int t){
    const long long INF = 0x1fffffffffffffff;
    vector<long long> cost((int) G.size(), INF);
    vector<int> par((int) G.size(), -1);
    using P = pair<long long, long long>;
    priority_queue<P, vector<P>, greater<>> q;
    cost[s] = 0;
    par[s] = -1;
    q.emplace(0, s);

    while(q.size()){
        auto [c, at] = q.top();
        q.pop();
        if(c > cost[at]) continue;
        for(auto &[to, t] : G[at]){
            if(cost[to] > c + t){
                par[to] = at;
                cost[to] = c + t;
                q.emplace(cost[to], to);
            }
        }
    }

    if(cost[t] == INF){
        return {-1, {}};
    }
    vector<pair<int, int>> path;
    for(int now = t; par[now] != -1; now = par[now]){
        path.emplace_back(par[now], now);
    }
    reverse(path.begin(), path.end());

    return {cost[t], path};
}
#line 2 "lib/graph/scc.hpp"

/**
 * @brief Strongly Connected Component (強連結成分分解)
 * @docs docs/graph/scc.md
 */

#line 11 "lib/graph/scc.hpp"

struct SCC{
    int siz;
    std::vector<std::vector<int>> G, G_reverse, G_compress;
    std::vector<bool> check;
    std::vector<int> memo, id;
    std::vector<int> s;
    std::vector<std::vector<int>> result;

    SCC(const int N) : siz(N), G(N), G_reverse(N), check(N), id(N){ }

    void add_edge(int u, int v){
        assert(0 <= u && u < siz);
        assert(0 <= v && v < siz);
        G[u].emplace_back(v);
    }

    void build(){
        for(int i = 0; i < siz; ++i){
            for(const auto &x : G[i]){
                G_reverse[x].emplace_back(i);
            }
        }

        for(int i = 0; i < siz; ++i){
            if(!check[i]){
                dfs(G, i);
            }
        }
        reverse(memo.begin(), memo.end());

        for(int i = 0; i < siz; ++i) check[i] = false;
        for(const auto &x : memo){
            if(!check[x]){
                s = {};
                dfs2(G_reverse, x);
                for(const auto &y : s){
                    id[y] = (int) result.size();
                }
                result.emplace_back(s);
            }
        }

        G_compress.resize(result.size());
        for(int i = 0; i < siz; ++i){
            for(const auto &x : G[i]){
                if(id[i] != id[x]){
                    G_compress[id[i]].emplace_back(id[x]);
                }
            }
        }
    }

    void dfs(const std::vector<std::vector<int>> &G, int curr){
        check[curr] = true;
        for(const auto &x : G[curr]){
            if(check[x]){
                continue;
            }
            dfs(G, x);
        }
        memo.emplace_back(curr);
    }

    void dfs2(const std::vector<std::vector<int>> &G, int curr){
        s.emplace_back(curr);
        check[curr] = true;
        for(const auto &x : G[curr]){
            if(check[x]){
                continue;
            }
            dfs2(G, x);
        }
    }

    std::vector<std::vector<int>> get() const {
        return result;
    }

    std::vector<std::vector<int>> getCompressed() const {
        return G_compress;
    }

    int getId(int x) const {
        return id[x];
    }
};
#line 7 "test/library_checker/graph/cycle_detection.test.cpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<int> u(m), v(m);
    map<pair<int, int>, int> e;
    for(int i = 0; i < m; i++){
        cin >> u[i] >> v[i];
        e[{u[i], v[i]}] = i;
    }
    vector<vector<int>> G(n);
    SCC scc(n);
    vector<vector<array<long long, 2>>> G2(n);
    for(int i = 0; i < m; i++){
        scc.add_edge(u[i], v[i]);
        G2[u[i]].push_back({v[i], 1});
    }
    scc.build();
    vector<int> ans;
    for(auto &s : scc.get()){
        int sizs = s.size();
        if(sizs == 1) continue;
        auto [w1, e1] = shortest_path(G2, s[0], s[1]);
        auto [w2, e2] = shortest_path(G2, s[1], s[0]);
        for(auto [a, b] : e1){
            ans.push_back(e[{a, b}]);
        }
        for(auto [a, b] : e2){
            ans.push_back(e[{a, b}]);
        }
        break;
    }

    int siz = ans.size();
    if(siz == 0){
        cout << -1 << "\n";
        return 0;
    }
    cout << siz << "\n";
    for(int i = 0; i < siz; i++){
        cout << ans[i] << "\n";
    }
}
Back to top page