Submit Info #34855

Problem Lang User Status Time Memory
Cycle Detection cpp mttk1528 AC 413 ms 46.67 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.66 MiB
example_01 AC 0 ms 0.62 MiB
example_02 AC 1 ms 0.59 MiB
random_00 AC 413 ms 43.98 MiB
random_01 AC 389 ms 46.67 MiB
random_02 AC 259 ms 29.36 MiB
random_03 AC 26 ms 14.42 MiB
random_04 AC 73 ms 16.74 MiB
random_05 AC 396 ms 40.73 MiB
random_06 AC 206 ms 32.92 MiB
random_07 AC 8 ms 4.17 MiB
random_08 AC 242 ms 32.50 MiB
random_09 AC 120 ms 18.23 MiB
random_dag_00 AC 370 ms 43.30 MiB
random_dag_01 AC 380 ms 45.93 MiB
random_dag_02 AC 264 ms 29.05 MiB
random_dag_03 AC 25 ms 14.42 MiB
random_dag_04 AC 71 ms 16.55 MiB
random_dag_05 AC 358 ms 40.05 MiB
random_dag_06 AC 201 ms 32.55 MiB
random_dag_07 AC 8 ms 4.30 MiB
random_dag_08 AC 260 ms 31.92 MiB
random_dag_09 AC 126 ms 18.05 MiB
random_dag_dense_00 AC 182 ms 15.17 MiB
random_dag_dense_01 AC 104 ms 4.17 MiB
random_dag_dense_02 AC 84 ms 3.42 MiB
random_dag_dense_03 AC 106 ms 4.17 MiB
random_dag_dense_04 AC 193 ms 11.80 MiB
random_dense_00 AC 220 ms 20.61 MiB
random_dense_01 AC 121 ms 6.05 MiB
random_dense_02 AC 92 ms 3.92 MiB
random_dense_03 AC 124 ms 6.05 MiB
random_dense_04 AC 239 ms 17.17 MiB

/** * author: zakhio (mttk1528) * created: 04.01.2021 03:05:41 **/ // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define dump(x) cout << #x << " = " << (x) << endl #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) #define len(x) (int)(x.size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define pcnt __builtin_popcount #define rup(x, y) ((x + y - 1) / (y)) using str = string; using ll = long long; using ld = long double; using pll = pair<ll,ll>; using pii = pair<int,int>; using pil = pair<int,ll>; using pli = pair<ll,int>; using pldld = pair<ld,ld>; const ld PI = acos(ld(-1.0)); const ld EPS = 1e-10; const ll LINF = 1e18; const int INF = 1e9; const int MAX = 2000020; const int MOD1 = 1000000007; const int MOD2 = 998244353; const int di[4] = {1, 0, -1, 0}; const int dj[4] = {0, 1, 0, -1}; const int di2[8] = {0, 1, 0, -1, 1, 1,-1, -1}; const int dj2[8] = {1, 0,-1, 0, 1, -1, 1, -1}; template <typename T> inline void print(T x) { cout << x << endl; return; } template <typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } template <typename T> inline bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; } template <typename T> T gcd_all(vector<T> &v) { return reduce(all(v), v[0], [](T x, T y) { return gcd(x, y); }); } template <typename T> T lcm_all(vector<T> &v) { return reduce(all(v), v[0], [](T x, T y) { return lcm(x, y); }); } template <typename T> T bpow(T a, int n) { T r(1); while (n) { if (n & 1) r *= a; a *= a; n >>= 1; } return r; } template <typename T> auto comp(vector<T> v) { sort(all(v)); v.erase(unique(all(v)), v.end()); return v; } template <typename T> string join(string s, vector<T> v) { string t = ""; rep(i, len(v)) { if (i) t += s; t += to_string(v[i]); } return t; } template <typename T> ld eucdist(pair<T,T> x, pair<T,T> y) { return hypotl(x.first - y.first, x.second - y.second); } template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T,U> &p) { return os << p.first << " " << p.second;} template <typename T, typename U> istream &operator>>(istream &is, pair<T,U> &p) { return is >> p.first >> p.second; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, len(v)) { if (i) os << " "; os << v[i]; } return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; } template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { int c(0); for (auto &x : st) { if (c) os << " "; os << x; c++; } return os;} struct CycleDetection { int n; bool dir, detected; vector<int> used, route; vector<vector<int>> adj; CycleDetection(int n_, bool d) : n(n_), dir(d), used(n_), adj(n_) {} void add_edge(int from, int to) { adj[from].emplace_back(to); if (!dir) adj[to].emplace_back(from); } int dfs(int v, int p) { used[v] = 1; route.emplace_back(v); for (int &u : adj[v]) { if ((!dir) && u == p) continue; if (used[u] == 2) continue; if (used[u] == 1) return u; int res = dfs(u, v); if (~res) return res; } used[v] = 2; route.pop_back(); return -1; } void exec() { for (int i = 0; i < n; i++) { if (used[i]) continue; int start = dfs(i, -1); if (!~start) continue; route.erase(route.begin(), find(route.begin(), route.end(), start)); detected = true; return; } detected = false; return; } }; void solve() { int n, m; cin >> n >> m; CycleDetection g(n, true); map<pii,int> mp; rep(i, m) { int a, b; cin >> a >> b; g.add_edge(a, b); mp[{a, b}] = i; } g.exec(); if (!g.detected) { print("-1"); } else { print(len(g.route)); rep(i, len(g.route)) { print(mp[{g.route[i], g.route[(i+1)%len(g.route)]}]); } } return; } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); // cout << fixed << setprecision(15); solve(); return 0; }