#include <bits/stdc++.h>
using namespace std;
#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl
#define fi first
#define se second
typedef pair<int, int> pii;
const int MaxN = 1010, MaxR = 1e5 + 10;
int n, r;
vector<pii> e[MaxN];
bool con[MaxN][MaxN];
pii edg[MaxR];
bool vis[MaxR], stk[MaxR];
int pre[MaxR];
void dfs(int x, int y, int id) {
vis[id] = true;
stk[id] = true;
// TRACE("+" _ id);
for (pii z : e[y]) {
if (!con[x][z.fi] && z.fi != x) {
if (!vis[z.se]) {
pre[z.se] = id;
dfs(y, z.fi, z.se);
} else if (stk[z.se]) {
// for (int q = id; q != z.se; q = pre[q]) TRACE(q _ edg[q].fi _ edg[q].se);
// TRACE(z.se _ edg[z.se].fi _ edg[z.se].se);
// TRACE(x _ y);
// exit(0);
// cout << endl;
vector<int> cyc = {x};
for (int q = pre[id]; q != z.se; q = pre[q])
cyc.push_back(edg[q].fi + edg[q].se - cyc.back());
if (cyc.back() != y) cyc.push_back(y);
// for(int i : cyc) TRACE(i);
// exit(0);
int m = cyc.size();
//for (int i = 0; i < m; i++)
// assert(!con[cyc[i]][cyc[(i + 2) % m]]);
/*
int pos[MaxN];
for (int i = 0; i < MaxN; i++) pos[i] = -1;
for (int i = path.size() - 1; i >= 0; i--) {
if (pos[path[i]] != -1) {
// TRACE(pos[path[i]] _ i);
// copy(path.begin() + pos[path[i]], path.begin() + i, cyc.begin());
//cyc = vector(path.begin() + pos[path[i]], path.begin() + i);
for (int j = pos[path[i]]; j > i; j--) cyc.push_back(path[j]);
break;
}
pos[path[i]] = i;
}
//for (int i : cyc) TRACE(i);
//exit(0);
for (int i = 0; i + 1 < cyc.size(); i++)
assert(con[cyc[i]][cyc[i+1]]);
assert(con[cyc[0]][cyc.back()]);
// exit(0);
*/
// int m = cyc.size();
//for (int i = 0; i < cyc.size();i++) {
// for(int j = (i + 2) % m; (j + 1) % m != i; j = (j + 1)% m)
// assert(!con[cyc[i]][cyc[j]]);
//}
// for (int i : cyc) cout << i << " "; cout << endl;
// for (int i = 0;i < m; i++) {
// for (int j = 0; j < m; j++) cout << con[cyc[i]][cyc[j]] << " ";
// cout << endl;
// }
for (int len = 3; len < m; len++)
for (int i = 0; i < m; i++) {
if (con[cyc[i]][cyc[(i + len) % m]]) {
// TRACE(i _ (i + len) % m);
for (int j = (i + 1) % m; j != i; j = (j + 1) % m)
cout << cyc[j] << " ";
cout << cyc[i];
/*
vector<int> kurac;
for (int j = (i + 1) % m; j != i; j = (j + 1) % m)
kurac.push_back(cyc[j]);
kurac.push_back(cyc[i]);
m = kurac.size();
for (int ii = 0; ii < kurac.size();ii++) {
for(int jj = (ii + 2) % m; (jj + 1) % m != ii; jj = (jj + 1)% m)
assert(!con[kurac[ii]][kurac[jj]]);
}
*/
exit(0);
}
}
// */
}
}
}
stk[id] = false;
// TRACE("-" _ id);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> r;
for (int i = 0; i < r; i++) {
int x, y;
cin >> x >> y;
e[x].push_back({y, i});
e[y].push_back({x, i});
con[x][y] = con[y][x] = true;
edg[i] = {x, y};
}
for (int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end());
for (int i = 0; i < r; i++) {
if (!vis[i]) {
dfs(edg[i].fi, edg[i].se, i);
}
}
cout << "no";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
576 KB |
Output is correct |
| 5 |
Correct |
2 ms |
576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
576 KB |
Output is correct |
| 2 |
Correct |
2 ms |
612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
868 KB |
Output is correct |
| 2 |
Correct |
2 ms |
868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1148 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1148 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
3324 KB |
Output is correct |
| 2 |
Correct |
13 ms |
3324 KB |
Output is correct |
| 3 |
Correct |
38 ms |
3324 KB |
Output is correct |
| 4 |
Correct |
14 ms |
3324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3324 KB |
Output is correct |
| 2 |
Correct |
12 ms |
3324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
3836 KB |
Output is correct |
| 2 |
Correct |
83 ms |
3976 KB |
Output is correct |
| 3 |
Correct |
25 ms |
3976 KB |
Output is correct |
| 4 |
Correct |
41 ms |
4052 KB |
Output is correct |
