Submit Info #31481

Problem Lang User Status Time Memory
Cycle Detection cpp harukiK AC 210 ms 59.37 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.61 MiB
example_01 AC 1 ms 0.67 MiB
example_02 AC 1 ms 0.64 MiB
random_00 AC 196 ms 51.31 MiB
random_01 AC 210 ms 59.37 MiB
random_02 AC 79 ms 15.88 MiB
random_03 AC 45 ms 38.86 MiB
random_04 AC 52 ms 27.80 MiB
random_05 AC 180 ms 42.17 MiB
random_06 AC 107 ms 47.23 MiB
random_07 AC 11 ms 9.42 MiB
random_08 AC 129 ms 35.61 MiB
random_09 AC 61 ms 14.79 MiB
random_dag_00 AC 166 ms 45.30 MiB
random_dag_01 AC 161 ms 52.05 MiB
random_dag_02 AC 77 ms 14.11 MiB
random_dag_03 AC 40 ms 39.17 MiB
random_dag_04 AC 50 ms 27.74 MiB
random_dag_05 AC 139 ms 38.36 MiB
random_dag_06 AC 104 ms 47.17 MiB
random_dag_07 AC 10 ms 9.42 MiB
random_dag_08 AC 111 ms 32.00 MiB
random_dag_09 AC 50 ms 14.80 MiB
random_dag_dense_00 AC 49 ms 10.05 MiB
random_dag_dense_01 AC 50 ms 9.30 MiB
random_dag_dense_02 AC 49 ms 9.38 MiB
random_dag_dense_03 AC 49 ms 9.25 MiB
random_dag_dense_04 AC 59 ms 11.42 MiB
random_dense_00 AC 51 ms 11.67 MiB
random_dense_01 AC 52 ms 11.17 MiB
random_dense_02 AC 50 ms 10.80 MiB
random_dense_03 AC 49 ms 11.24 MiB
random_dense_04 AC 58 ms 10.05 MiB

// >>> TEMPLATES #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; #define int ll #define double ld #define rep(i,n) for (int i = 0; i < (int)(n); i++) #define rep1(i,n) for (int i = 1; i <= (int)(n); i++) #define repR(i,n) for (int i = (int)(n)-1; i >= 0; i--) #define rep1R(i,n) for (int i = (int)(n); i >= 1; i--) #define loop(i,a,B) for (int i = a; i B; i++) #define loopR(i,a,B) for (int i = a; i B; i--) #define all(x) begin(x), end(x) #define allR(x) rbegin(x), rend(x) #define rng(x,l,r) begin(x) + (l), begin(x) + (r) #define pb push_back #define eb emplace_back #define mp make_pair #define fst first #define snd second template <class Int> auto constexpr inf = numeric_limits<Int>::max()/2-1; auto constexpr INF32 = inf<int32_t>; auto constexpr INF64 = inf<int64_t>; auto constexpr INF = inf<int>; #ifdef LOCAL #include "debug.hpp" #else #define dump(...) (void)(0) #define say(x) (void)(0) #define debug if (0) #endif template <class T, class Comp> struct pque : priority_queue<T, vector<T>, Comp> { vector<T> &data() { return this->c; } void clear() { this->c.clear(); } }; template <class T> using pque_max = pque<T, less<T>>; template <class T> using pque_min = pque<T, greater<T>>; template <class T, class = typename T::iterator, enable_if_t<!is_same<T, string>::value, int> = 0> ostream& operator<<(ostream& os, T const& a) { bool f = true; for (auto const& x : a) os << (f ? "" : " ") << x, f = false; return os; } template <class T, size_t N, enable_if_t<!is_same<T, char>::value, int> = 0> ostream& operator<<(ostream& os, const T (&a)[N]) { bool f = true; for (auto const& x : a) os << (f ? "" : " ") << x, f = false; return os; } template <class T, class = decltype(begin(declval<T&>())), class = typename enable_if<!is_same<T, string>::value>::type> istream& operator>>(istream& is, T &a) { for (auto& x : a) is >> x; return is; } template <class T, class S> ostream& operator<<(ostream& os, pair<T,S> const& p) { return os << p.first << " " << p.second; } template <class T, class S> istream& operator>>(istream& is, pair<T,S>& p) { return is >> p.first >> p.second; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } iosetup; template <class F> struct FixPoint : private F { constexpr FixPoint(F&& f) : F(forward<F>(f)) {} template <class... T> constexpr auto operator()(T&&... x) const { return F::operator()(*this, forward<T>(x)...); } }; struct MakeFixPoint { template <class F> constexpr auto operator|(F&& f) const { return FixPoint<F>(forward<F>(f)); } }; #define MFP MakeFixPoint()| #define def(name, ...) auto name = MFP [&](auto &&name, __VA_ARGS__) template <class T, size_t d> struct vec_impl { using type = vector<typename vec_impl<T,d-1>::type>; template <class... U> static type make_v(size_t n, U&&... x) { return type(n, vec_impl<T,d-1>::make_v(forward<U>(x)...)); } }; template <class T> struct vec_impl<T,0> { using type = T; static type make_v(T const& x = {}) { return x; } }; template <class T, size_t d = 1> using vec = typename vec_impl<T,d>::type; template <class T, size_t d = 1, class... Args> auto make_v(Args&&... args) { return vec_impl<T,d>::make_v(forward<Args>(args)...); } template <class T> void quit(T const& x) { cout << x << endl; exit(0); } template <class T, class U> constexpr bool chmin(T& x, U const& y) { if (x > y) { x = y; return true; } return false; } template <class T, class U> constexpr bool chmax(T& x, U const& y) { if (x < y) { x = y; return true; } return false; } template <class It> constexpr auto sumof(It b, It e) { return accumulate(b, e, typename iterator_traits<It>::value_type{}); } template <class T> int sz(T const& x) { return x.size(); } template <class C, class T> int lbd(C const& v, T const& x) { return lower_bound(begin(v), end(v), x)-begin(v); } template <class C, class T> int ubd(C const& v, T const& x) { return upper_bound(begin(v), end(v), x)-begin(v); } const int dx[] = { 1,0,-1,0,1,-1,-1,1 }; const int dy[] = { 0,1,0,-1,1,1,-1,-1 }; constexpr int popcnt(ll x) { return __builtin_popcountll(x); } // [a,b] template <class Int> Int rand(Int a, Int b) { static mt19937_64 mt{random_device{}()}; return uniform_int_distribution<Int>(a,b)(mt); } i64 irand(i64 a, i64 b) { return rand<i64>(a,b); } u64 urand(u64 a, u64 b) { return rand<u64>(a,b); } // <<< // >>> scc constexpr int dst(int v) { return v; } template <class E, class = decltype(declval<E>().to)> constexpr int dst(E const& e) { return e.to; } template <class E> struct SCC { vector<vector<E>> const& g; vector<int32_t> ord, low, st; int32_t time = 0, pos = 0, sz = 0; SCC(vector<vector<E>> const& g) : g(g), ord(g.size()), low(g.size()), st(g.size()) { rep (v,g.size()) if (ord[v] == 0) dfs(v); for (auto &x : ord) x += sz; } void dfs(int32_t v) { low[v] = ord[v] = ++time; st[pos++] = v; for (auto const& e : g[v]) { if (ord[dst(e)] == 0) { dfs(dst(e)); chmin(low[v], low[dst(e)]); } else if (ord[dst(e)] > 0) { chmin(low[v], ord[dst(e)]); } } if (low[v] == ord[v]) { sz++; do ord[st[--pos]] = -sz; while (st[pos] != v); } } // t-sorted id int id(int v) const { return ord[v]; } int size() const { return sz; } vector<vector<int>> groups() const { vector<vector<int>> grp(sz); rep (v,g.size()) grp[ord[v]].push_back(v); return grp; } // no multiple edges, no self-loops // no edge information vector<vector<int>> graph() const { vector<vector<int>> ret(size()); rep (v,g.size()) { for (auto const& e : g[v]) { int x = id(v), y = id(dst(e)); if (x != y) ret[x].push_back(y); } } for (auto &ls : ret) { sort(ls.begin(), ls.end()); ls.erase(unique(ls.begin(), ls.end()), ls.end()); } return ret; } }; template <class E> auto get_scc(vector<vector<E>> const& g) { return SCC<E>(g); } // <<< int32_t main() { int n, m; cin >> n >> m; struct edge { int to, id; }; vector<vector<edge>> g(n); rep (i,m) { int a, b; cin >> a >> b; g[a].pb({b, i}); } auto scc = get_scc(g); auto grp = scc.groups(); int ii = -1; repR (i,scc.size()) if (sz(grp[i]) > 1) ii = i; if (ii < 0) quit(-1); auto v = grp[ii]; vector<edge> nxt(n, {-1,-1}); for (int x : v) { for (auto e : g[x]) { if (scc.id(x) == scc.id(e.to)) { nxt[x] = e; break; } } assert(nxt[x].to >= 0); } int x = v[0], y = v[0]; do { x = nxt[x].to; y = nxt[nxt[y].to].to; } while (x != y); vector<int> cyc; do { cyc.eb(nxt[x].id); x = nxt[x].to; y = nxt[nxt[y].to].to; } while (x != y); cout << cyc.size() << endl; for (int id : cyc) cout << id << "\n"; }