#include<stdio.h>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
vector<int>edge[1212], E[1212];
int depth[1212], is_gone_dfs1[1212];
set<pair<int, int>>L[1212]; set<int>M[1212];
bool sort_e(int a, int b) { return depth[a] < depth[b]; }
void dfs1(int w,int dep,int bef) {
depth[w] = dep; is_gone_dfs1[w] = 1;
for (int i = 0; i < edge[w].size(); i++) {
int next = edge[w][i];
if (is_gone_dfs1[next]) {
if(next==bef || depth[next] > depth[w])continue;
L[w].insert({ depth[next],next });
continue;
}
E[w].push_back(next);
dfs1(next, dep + 1, w);
}
}
int stdep, D[1212], st, go[1212], R[1212], cck, NT[1212];
int dfs2(int w, int bef) {
set<pair<int, int>>::iterator it = L[w].lower_bound({ stdep + 1,-1e9 });
if (bef != -1 && it == L[w].end())D[w] = D[bef] + 1, go[w] = bef, R[w] = R[bef];
if (bef != -1 && it != L[w].end())D[w] = D[it->second] + 1, go[w] = it->second, R[w] = R[it->second];
if (M[w].find(st) != M[w].end()) {
if (D[w] >= 4)return w;
if (D[w] == 3) {
int x = go[w];
for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)NT[edge[w][i]] = 1;
for (int i = 0; i < edge[w].size(); i++) {
if (D[edge[w][i]] >= 3 && R[x] != R[edge[w][i]] && !NT[R[edge[w][i]]]) {
go[w] = edge[w][i];
return w;
}
}
for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)NT[edge[w][i]] = 0;
}
D[w] = 2, go[w] = st; R[w] = w;
}
for (int i = 0; i < E[w].size(); i++){
int next = E[w][i];
int k = dfs2(next, w);
if (k) return k;
}
return 0;
}
int main() {
int n, m; scanf("%d%d", &n, &m);
int i, j;
for (i = 0; i < m; i++) {
int s, e; scanf("%d%d", &s, &e);
edge[s].push_back(e); M[s].insert(e);
edge[e].push_back(s); M[e].insert(s);
}
for (i = 1; i <= n; i++) {
if (is_gone_dfs1[i])continue;
dfs1(i, 1, -1);
}
for (i = 1; i <= n; i++)sort(edge[i].begin(), edge[i].end(),sort_e);
for (i = 1; i <= n; i++) {
D[i] = 1; R[i] = st = i; stdep = depth[i];
int now = dfs2(i, -1);
if (now) {
while (now != i) {
printf("%d ", now);
now = go[now];
}
printf("%d ", i);
return 0;
}
for (j = 1; j <= n; j++)D[j] = R[j] = go[j] = 0;
}
printf("no");
return 0;
}
Compilation message
indcyc.cpp: In function 'void dfs1(int, int, int)':
indcyc.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edge[w].size(); i++) {
~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int dfs2(int, int)':
indcyc.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)NT[edge[w][i]] = 1;
~~^~~~~~~~~~~~~~~~
indcyc.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edge[w].size(); i++) {
~~^~~~~~~~~~~~~~~~
indcyc.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edge[w].size(); i++) if (D[edge[w][i]] == 2)NT[edge[w][i]] = 0;
~~^~~~~~~~~~~~~~~~
indcyc.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E[w].size(); i++){
~~^~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:51:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, m; scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int s, e; scanf("%d%d", &s, &e);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
612 KB |
Output is correct |
| 3 |
Correct |
2 ms |
612 KB |
Output is correct |
| 4 |
Correct |
2 ms |
612 KB |
Output is correct |
| 5 |
Correct |
3 ms |
612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
828 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1256 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1256 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1640 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1640 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
8116 KB |
Output is correct |
| 2 |
Correct |
59 ms |
8116 KB |
Output is correct |
| 3 |
Correct |
246 ms |
8116 KB |
Output is correct |
| 4 |
Correct |
95 ms |
8116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
8116 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
413 ms |
15340 KB |
Output is correct |
| 2 |
Correct |
476 ms |
15356 KB |
Output is correct |
| 3 |
Correct |
221 ms |
15356 KB |
Output is correct |
| 4 |
Correct |
245 ms |
15356 KB |
Output is correct |
