This documentation is automatically generated by competitive-verifier/competitive-verifier
// @brief Cycle Detection (Undirected)
#define PROBLEM "https://judge.yosupo.jp/problem/cycle_detection_undirected"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#include "cp-algo/graph/cycle.hpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::graph;
void solve() {
int n, m;
cin >> n >> m;
graph<undirected> g(n);
g.read_edges(m);
auto res = find_cycle(g);
if(empty(res)) {
cout << -1 << "\n";
} else {
ranges::reverse(res);
cout << size(res) << "\n";
for(auto it: res) {cout << g.edge(it).to << ' ';}
cout << "\n";
for(auto it: res) {cout << it / 2 << ' ';}
cout << "\n";
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--) {
solve();
}
}
#line 1 "verify/graph/cycle_undirected.test.cpp"
// @brief Cycle Detection (Undirected)
#define PROBLEM "https://judge.yosupo.jp/problem/cycle_detection_undirected"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("tune=native")
#line 1 "cp-algo/graph/cycle.hpp"
#line 1 "cp-algo/graph/base.hpp"
#line 1 "cp-algo/graph/edge_types.hpp"
#include <iostream>
#include <cstdint>
namespace cp_algo::graph {
using node_index = int;
struct edge_base {
node_index to;
edge_base() {}
edge_base(node_index v): to(v) {}
static auto read(node_index v0 = 0) {
node_index u, v;
std::cin >> u >> v;
return std::pair{u - v0, edge_base(v - v0)};
}
edge_base backedge(int from) const {
return {from};
}
};
struct weighted_edge: edge_base {
int64_t w;
weighted_edge() {}
weighted_edge(node_index v, int64_t w): edge_base(v), w(w) {}
static auto read(node_index v0 = 0) {
node_index u, v;
int64_t w;
std::cin >> u >> v >> w;
return std::pair{u - v0, weighted_edge{v - v0, w}};
}
weighted_edge backedge(node_index from) const {
return {from, w};
}
};
template<typename edge>
concept edge_type = std::is_base_of_v<edge_base, edge>;
template<typename edge>
concept weighted_edge_type = std::is_base_of_v<weighted_edge, edge>;
}
#line 1 "cp-algo/data_structures/stack_union.hpp"
#include <cstddef>
#include <vector>
namespace cp_algo::data_structures {
template<class datatype>
struct stack_union {
stack_union(int n = 0): head(n), next(1), data(1) {}
void push(int v, datatype const& vdata) {
next.push_back(head[v]);
head[v] = std::size(next) - 1;
data.push_back(vdata);
}
template<typename... Args>
void emplace(int v, Args&&... vdata) {
next.push_back(head[v]);
head[v] = size(next) - 1;
data.emplace_back(std::forward<Args...>(vdata...));
}
void reserve(int m) {
data.reserve(m);
next.reserve(m);
}
size_t size() const {return std::size(head);}
size_t nodes() const {return std::size(data);}
std::vector<int> head, next;
std::vector<datatype> data;
};
}
#line 5 "cp-algo/graph/base.hpp"
#include <ranges>
#line 7 "cp-algo/graph/base.hpp"
namespace cp_algo::graph {
using edge_index = int;
enum type {directed = 0, undirected = 1};
template<type _undirected, edge_type edge_t = edge_base>
struct graph {
static constexpr bool undirected = _undirected;
graph(int n, int v0 = 0): v0(v0), adj(n) {}
void add_edge(node_index u, edge_t e) {
adj.push(u, size(edges));
edges.push_back(e);
if constexpr (undirected) {
adj.push(e.to, size(edges));
}
edges.push_back(e.backedge(u));
}
void read_edges(node_index m) {
adj.reserve(m);
for(edge_index i = 0; i < m; i++) {
auto [u, e] = edge_t::read(v0);
add_edge(u, e);
}
}
void call_adjacent(node_index v, auto &&callback, auto &&terminate) const {
for(int sv = adj.head[v]; sv && !terminate(); sv = adj.next[sv]) {
callback(adj.data[sv]);
}
}
void call_adjacent(node_index v, auto &&callback) const {
call_adjacent(v, callback, [](){return false;});
}
void call_edges(auto &&callback) const {
for(edge_index e: edges_view()) {
callback(e);
}
}
auto nodes_view() const {
return std::views::iota(0, n());
}
auto edges_view() const {
return std::views::filter(
std::views::iota(0, 2 * m()),
[](edge_index e) {return !(e % 2);}
);
}
auto const& incidence_lists() const {return adj;}
edge_t const& edge(edge_index e) const {return edges[e];}
node_index n() const {return adj.size();}
edge_index m() const {return size(edges) / 2;}
private:
node_index v0;
std::vector<edge_t> edges;
data_structures::stack_union<edge_index> adj;
};
}
#line 4 "cp-algo/graph/cycle.hpp"
#include <algorithm>
#line 6 "cp-algo/graph/cycle.hpp"
namespace cp_algo::graph {
std::vector<int> find_cycle(auto const& g) {
std::vector<char> state(g.n());
std::vector<int> cycle;
auto dfs = [&](auto &&self, int v, int pe) -> bool {
state[v] = 1;
bool found = false;
g.call_adjacent(v, [&](int e) {
if(e / 2 != pe / 2) {
int u = g.edge(e).to;
if(state[u] == 0) {
if(self(self, u, e)) {
if(g.edge(cycle[0]).to != g.edge(cycle.back() ^ 1).to) {
cycle.push_back(e);
}
found = true;
}
} else if(state[u] == 1) {
cycle = {e};
found = true;
}
}
}, [&found](){return found;});
state[v] = 2;
return found;
};
for(int i: g.nodes_view()) {
if(!state[i] && dfs(dfs, i, -2)) {
break;
}
}
std::ranges::reverse(cycle);
return cycle;
}
}
#line 6 "verify/graph/cycle_undirected.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::graph;
void solve() {
int n, m;
cin >> n >> m;
graph<undirected> g(n);
g.read_edges(m);
auto res = find_cycle(g);
if(empty(res)) {
cout << -1 << "\n";
} else {
ranges::reverse(res);
cout << size(res) << "\n";
for(auto it: res) {cout << g.edge(it).to << ' ';}
cout << "\n";
for(auto it: res) {cout << it / 2 << ' ';}
cout << "\n";
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--) {
solve();
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 | AC | 5 ms | 4 MB |
g++ | example_01 | AC | 4 ms | 4 MB |
g++ | example_02 | AC | 4 ms | 3 MB |
g++ | example_03 | AC | 4 ms | 4 MB |
g++ | example_04 | AC | 4 ms | 4 MB |
g++ | long_cycle_00 | AC | 127 ms | 53 MB |
g++ | long_cycle_01 | AC | 127 ms | 53 MB |
g++ | long_cycle_02 | AC | 22 ms | 9 MB |
g++ | random_00 | AC | 52 ms | 20 MB |
g++ | random_01 | AC | 54 ms | 21 MB |
g++ | random_02 | AC | 45 ms | 19 MB |
g++ | random_03 | AC | 14 ms | 6 MB |
g++ | random_04 | AC | 25 ms | 8 MB |
g++ | random_05 | AC | 51 ms | 20 MB |
g++ | random_06 | AC | 36 ms | 13 MB |
g++ | random_07 | AC | 8 ms | 4 MB |
g++ | random_08 | AC | 41 ms | 19 MB |
g++ | random_09 | AC | 27 ms | 11 MB |
g++ | random_dense_00 | AC | 42 ms | 19 MB |
g++ | random_dense_01 | AC | 44 ms | 19 MB |
g++ | random_dense_02 | AC | 44 ms | 19 MB |
g++ | tree_00 | AC | 70 ms | 20 MB |
g++ | tree_01 | AC | 83 ms | 21 MB |
g++ | tree_02 | AC | 15 ms | 5 MB |
g++ | unicyclic_00 | AC | 62 ms | 20 MB |
g++ | unicyclic_01 | AC | 63 ms | 21 MB |
g++ | unicyclic_02 | AC | 14 ms | 5 MB |