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_undirected.test.cpp

Depends on

Code

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

#include "../../../lib/data_structure/union_find.hpp"
#include "../../../lib/graph/dijkstra.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;
        e[{v[i], u[i]}] = i;
    }
    vector<vector<array<long long, 2>>> G(n);
    UnionFind uf(n);
    vector<int> ansv, anse;
    for(int i = 0; i < m; i++){
        if(uf.same(u[i], v[i])){
            auto [w, path] = shortest_path(G, u[i], v[i]);
            ansv.push_back(u[i]);
            for(auto [x, y] : path){
                ansv.push_back(y);
                anse.push_back(e[{x, y}]);
            }
            anse.push_back(i);
            break;
        }
        uf.unite(u[i], v[i]);
        G[u[i]].push_back({v[i], 1});
        G[v[i]].push_back({u[i], 1});
    }
    
    int siz = ansv.size();
    if(siz == 0){
        cout << -1 << "\n";
        return 0;
    }
    cout << siz << "\n";
    for(int i = 0; i < siz; i++){
        cout << ansv[i] << " \n"[i == siz - 1];
    }
    for(int i = 0; i < siz; i++){
        cout << anse[i] << " \n"[i == siz - 1];
    }
}
#line 1 "test/library_checker/graph/cycle_detection_undirected.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cycle_detection_undirected"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/data_structure/union_find.hpp"

/**
 * @brief Union-Find
 * @docs docs/data_structure/union_find.md
 */

#line 10 "lib/data_structure/union_find.hpp"

struct UnionFind{
    int V;
    std::vector<int> par;
    std::vector<int> edg;

    UnionFind(const int N) : V(N), par(N), edg(N){
        for(int i = 0; i < N; ++i){
            par[i] = -1;
            edg[i] = 0;
        }
    }

    int root(int x){
        assert(0 <= x && x < V);
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    int unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry){
            edg[rx]++;
            return rx;
        }
        if(-par[rx] < -par[ry]) std::swap(rx, ry);
        par[rx] = par[rx] + par[ry];
        par[ry] = rx;
        edg[rx] += edg[ry] + 1;
        return rx;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    long long size(int x){
        return -par[root(x)];
    }

    long long edge(int x){
        return edg[root(x)];
    }
};
#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 7 "test/library_checker/graph/cycle_detection_undirected.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;
        e[{v[i], u[i]}] = i;
    }
    vector<vector<array<long long, 2>>> G(n);
    UnionFind uf(n);
    vector<int> ansv, anse;
    for(int i = 0; i < m; i++){
        if(uf.same(u[i], v[i])){
            auto [w, path] = shortest_path(G, u[i], v[i]);
            ansv.push_back(u[i]);
            for(auto [x, y] : path){
                ansv.push_back(y);
                anse.push_back(e[{x, y}]);
            }
            anse.push_back(i);
            break;
        }
        uf.unite(u[i], v[i]);
        G[u[i]].push_back({v[i], 1});
        G[v[i]].push_back({u[i], 1});
    }
    
    int siz = ansv.size();
    if(siz == 0){
        cout << -1 << "\n";
        return 0;
    }
    cout << siz << "\n";
    for(int i = 0; i < siz; i++){
        cout << ansv[i] << " \n"[i == siz - 1];
    }
    for(int i = 0; i < siz; i++){
        cout << anse[i] << " \n"[i == siz - 1];
    }
}
Back to top page