Submit Info #43344

Problem Lang User Status Time Memory
Cycle Detection cpp Felerius AC 155 ms 20.52 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.68 MiB
example_01 AC 2 ms 0.68 MiB
example_02 AC 1 ms 0.68 MiB
random_00 AC 128 ms 18.30 MiB
random_01 AC 155 ms 20.52 MiB
random_02 AC 72 ms 7.34 MiB
random_03 AC 17 ms 11.68 MiB
random_04 AC 36 ms 9.80 MiB
random_05 AC 101 ms 15.93 MiB
random_06 AC 69 ms 17.30 MiB
random_07 AC 5 ms 3.30 MiB
random_08 AC 80 ms 13.23 MiB
random_09 AC 39 ms 6.68 MiB
random_dag_00 AC 130 ms 17.80 MiB
random_dag_01 AC 117 ms 19.93 MiB
random_dag_02 AC 69 ms 7.30 MiB
random_dag_03 AC 14 ms 11.72 MiB
random_dag_04 AC 31 ms 9.71 MiB
random_dag_05 AC 100 ms 15.39 MiB
random_dag_06 AC 77 ms 17.01 MiB
random_dag_07 AC 5 ms 3.33 MiB
random_dag_08 AC 87 ms 12.84 MiB
random_dag_09 AC 42 ms 6.43 MiB
random_dag_dense_00 AC 48 ms 5.68 MiB
random_dag_dense_01 AC 50 ms 5.05 MiB
random_dag_dense_02 AC 48 ms 5.43 MiB
random_dag_dense_03 AC 51 ms 5.31 MiB
random_dag_dense_04 AC 56 ms 6.30 MiB
random_dense_00 AC 48 ms 6.68 MiB
random_dense_01 AC 49 ms 6.31 MiB
random_dense_02 AC 47 ms 5.93 MiB
random_dense_03 AC 50 ms 6.33 MiB
random_dense_04 AC 53 ms 5.30 MiB

#pragma GCC optimize("fast-math") // begin "cp-lib/boilerplate.hpp" #include <bits/stdc++.h> #define _choose(_1, _2, _3, chosen, ...) chosen #define _rep(i, l, r) for (int i = l; i < r; ++i) #define _rep0(i, r) _rep(i, 0, r) #define _repr(i, r, l) for (int i = r; i >= l; --i) #define _repr0(i, r) _repr(i, r, 0) #define rep(...) _choose(__VA_ARGS__, _rep, _rep0, suppress_warning)(__VA_ARGS__) #define repr(...) _choose(__VA_ARGS__, _repr, _repr0, suppress_warning)(__VA_ARGS__) #define all(a) ::begin(a),::end(a) #define sz(c) int(::size(c)) #define trav(a, b) for(auto& a : b) using namespace std; using ll = long long; using ld = long double; using u64 = uint64_t; using u32 = uint32_t; [[maybe_unused]] static constexpr int INF = int(1e9 + 5); [[maybe_unused]] static constexpr ll INFL = ll(INF) * INF; [[maybe_unused]] static mt19937 rng(u32(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count())); namespace cp_lib {} // end "cp-lib/boilerplate.hpp" // begin "cp-lib/graph/cycle.hpp" namespace cp_lib { template <bool Directed, class C, class To> vector<int> find_cycle(const vector<C>& adj, To&& to) { vector<int> p; vector state(sz(adj), uint8_t(0)); auto dfs = [&](int v, auto&& self) -> bool { state[v] = 1; p.push_back(v); trav(e, adj[v]) { if (state[to(e)] == 2) continue; if (state[to(e)] == 1) { if (!Directed && sz(p) > 1 && p[sz(p) - 2] == to(e)) continue; p.erase(begin(p), find(all(p), to(e))); return true; } if (self(to(e), self)) return true; } state[v] = 2; p.pop_back(); return false; }; rep(i, sz(adj)) if (!state[i] && dfs(i, dfs)) return p; return {}; } template <bool Directed, class C> vector<int> find_cycle(const vector<C>& adj) { return find_cycle<Directed>(adj, [](int v) { return v; }); } } // end "cp-lib/graph/cycle.hpp" #define PROBLEM "https://judge.yosupo.jp/problem/cycle_detection" using namespace cp_lib; int main() { cin.tie(0)->sync_with_stdio(false); int n, m; cin >> n >> m; vector adj(n, vector<pair<int, int>>()); rep(i, m) { int u, v; cin >> u >> v; adj[u].emplace_back(v, i); } auto cycle = find_cycle<true>(adj, [](auto e) { return e.first; }); if (!sz(cycle)) cout << "-1\n", exit(0); cout << sz(cycle) << '\n'; rep(i, sz(cycle)) { int u = cycle[i], v = cycle[(i + 1) % sz(cycle)]; int j = 0; while (adj[u][j].first != v) ++j; cout << adj[u][j].second << '\n'; } }