#include <bits/stdc++.h>
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1000 + 7, mod = 1e9 + 7;
const ll inf = 2e18;
// How interesting!
int n, m, t;
int st[N], prv[N];
vector<int> adj[N];
map<pii, int> ed;
void cycle(vector<int> v, int x, int y)
{
int k = 0;
while (x != y)
{
v.push_back(x);
x = prv[x];
}
int sz = (int)v.size();
if (sz < 4)
return;
bool bad = 0;
for (int i = 0; i < sz; ++i)
{
for (int j = 0; j < sz; ++j)
{
if (i == j || (i + 1) % sz == j || (j + 1) % sz == i)
continue;
if (ed[{v[i], v[j]}])
{
i = j = sz;
bad = 1;
break;
}
}
}
if (!bad)
{
for (auto u : v)
cout << u << " ";
exit(0);
}
}
void dfs(int x, int p)
{
st[x] = ++t;
prv[x] = p;
for (auto u : adj[x])
{
if (u == p)
continue;
if (st[u])
{
if (st[u] < st[x])
{
cycle({u}, x, u);
}
else
{
cycle({x}, u, x);
}
}
else
{
dfs(u, x);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("in.in", "r", stdin);
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int u, v;
cin >> u >> v;
bool bad = 0;
for (int j = 1; j <= n; ++j)
{
if (ed[{j, u}] && ed[{j, v}])
{
bad = 1;
break;
}
}
if (bad)
continue;
adj[u].push_back(v);
adj[v].push_back(u);
ed[{u, v}] = ed[{v, u}] = 1;
}
for (int i = 1; i <= n; ++i)
{
memset(st, 0, sizeof st);
memset(prv, 0, sizeof prv);
t = 0;
dfs(i, i);
}
cout << "no";
return 0;
}
/*
- bounds sir (segtree = 4N, eulerTour = 2N, ...)
- a variable defined twice?
- will overflow?
- is it a good complexity?
- don't mess up indices (0-indexed vs 1-indexed)
- reset everything between testcases.
*/
Compilation message
indcyc.cpp: In function 'void cycle(std::vector<int>, int, int)':
indcyc.cpp:32:13: warning: unused variable 'k' [-Wunused-variable]
32 | int k = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong adjacency |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
896 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
6140 KB |
Wrong answer on graph without induced cycle |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
4216 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1081 ms |
17564 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
30588 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1049 ms |
6896 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
