#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 1010;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;
int n, m;
vector< int > graph[maxn];
int eg[maxn][maxn];
bool bio[maxn];
bool er[maxn];
int dis[maxn];
queue< int > q;
void dfs(int x, vector< int > &v) {
bio[x] = true;
v.push_back(x);
for (int tren : graph[x]) {
if (!er[tren] && !bio[tren]) {
dfs(tren, v);
}
}
}
void solve(vector< int > v) {
if (v.size() == 0) return;
int x = v[0];
//printf("solve: ");
//for (int tren : v) printf("%d ", tren);
//printf("\n");
vector< int > s, p;
for (int i = 1; i < v.size(); i++) {
bio[v[i]] = false;
if (eg[x][v[i]]) s.push_back(v[i]);
else p.push_back(v[i]);
}
for (int i = 1; i <= n; i++) er[i] = false;
er[x] = true;
for (int tren : s) er[tren] = true;
vector< vector<int> > vs, acs;
for (int i = 0; i < p.size(); i++) {
if (bio[p[i]]) continue;
vector< int > tr;
dfs(p[i], tr);
vs.push_back(tr);
//printf("comp: ");
//for (int y : tr) printf("%d ", y);
//printf("\n");
}
for (auto ax : vs) {
vector< int > ps;
int a = -1, b = -1;
for (int tren : s) {
for (int ing : ax) {
if (eg[tren][ing]) {
for (int p : ps) {
if (eg[tren][p] == 0) {
a = p, b = tren;
break;
}
}
if (a == -1) ps.push_back(tren);
break;
}
}
if (a != -1) break;
}
if (a == -1) continue;
//printf("found: %d %d\n", a, b);
for (int i = 1; i <= n; i++) dis[i] = -1;
for (int tren : ax) dis[tren] = inf;
dis[b] = inf, dis[a] = 0;
q.push(a);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int tren : graph[node]) {
if (dis[tren] == inf) {
dis[tren] = 1 + dis[node];
q.push(tren);
}
}
}
vector< int > sol;
int ptr = b;
while (ptr != a) {
sol.push_back(ptr);
for (int tren : graph[ptr]) {
if (dis[tren] + 1 == dis[ptr]) {
ptr = tren;
break;
}
}
}
reverse(sol.begin(), sol.end());
printf("%d %d ", x, a);
for (int tren : sol) printf("%d ", tren);
printf("\n");
exit(0);
}
solve(s);
for (int i = 0; i < vs.size(); i++) {
vector< int > tren = vs[i];
for (int ac : s) {
for (int ps : vs[i]) {
if (eg[ps][ac]) {
tren.push_back(ac);
break;
}
}
}
solve(tren);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
eg[a][b] = eg[b][a] = 1;
}
memset(er, false, sizeof er);
vector< int > v;
for (int i = 1; i <= n; i++)
v.push_back(i);
solve(v);
printf("no\n");
return 0;
}
Compilation message
indcyc.cpp: In function 'void solve(std::vector<int>)':
indcyc.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 1; i < v.size(); i++) {
| ~~^~~~~~~~~~
indcyc.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i < p.size(); i++) {
| ~~^~~~~~~~~~
indcyc.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 0; i < vs.size(); i++) {
| ~~^~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
139 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
716 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
716 KB |
Wrong answer on graph without induced cycle |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1612 KB |
Wrong answer on graph without induced cycle |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1484 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
5236 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
4704 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
3876 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
