This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m;
int nxt[N][N];
int par[N];
bool E[N][N];
bool finish[N][N];
vector<int> go;
void cal(int x, int y) {
vector<int > vx, vy;
while (par[x] != x) vx.push_back(x), x = par[x];
vx.push_back(x);
while (par[y] != y) vy.push_back(y), y = par[y];
reverse(vy.begin(), vy.end());
for (auto i : vy) vx.push_back(i);
for (auto i : vx) cout << i << ' ';
}
void trace() {
int sz = go.size();
for (auto i : go) par[i] = 0;
queue<int> qu;
par[go[0]] = go[0], qu.push(go[0]);
while (qu.size()) {
int u = qu.front(); qu.pop();
for (auto v : go) {
if (!E[u][v]) continue;
if (!par[v]) {
par[v] = u, qu.push(v);
}
else if (par[u] != v) {
cal(u, v); exit(0);
}
}
}
}
void dfs(int x, int y) {
for (int i = 1; i <= n; ++i) {
if (!E[y][i] || E[x][i]) continue;
if (nxt[y][i] < 0 || finish[y][i]) continue;
if (nxt[y][i] > 0) {
int curx = x, cury = y;
while (curx != y && cury != i) {
go.push_back(cury);
int tmp = nxt[curx][cury];
cury = curx, curx = tmp;
}
go.push_back(cury), trace();
}
else nxt[y][i] = x, nxt[i][y] = -x, dfs(y, i);
}
finish[x][y] = finish[y][x] = 1;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
E[u][v] = E[v][u] = 1;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (!E[i][j] || nxt[i][j]) continue;
nxt[i][j] = i, nxt[j][i] = -i, E[j][i] = 0, dfs(i, j);
}
}
cout << "no";
}
Compilation message (stderr)
indcyc.cpp: In function 'void trace()':
indcyc.cpp:24:6: warning: unused variable 'sz' [-Wunused-variable]
int sz = go.size();
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |