#include <bits/stdc++.h>
using namespace std;
vector<int> AdjList[1005];
bool visited[1005];
bool AdjMat[1005][1005];
int dist[1005];
int p[1005];
bool forbidden[1005];
int N, R;
vector<int> stack1;
bool picked[1005];
void dfs(int u, int s, int k){
/*printf("dfs(%d, %d, %d): ", u, s, k);
for(int x: stack1){
printf("%d ", x);
}
printf("\n");*/
if(k > N){return;}
if(u == s && k > 0){
if(k < 4){return;}
bool boleh = true;
for(int i = 0; i < (int)stack1.size()-1; i ++){
for(int j = i+2; j < (int)stack1.size()-1; j ++){
if(min(j-i, (int)stack1.size()-1-(j-i)) < 2){continue;}
int x = stack1[i];
int y = stack1[j];
if(AdjMat[x][y]){
//printf("%d and %d connected\n", x, y);
boleh = false;
break;
}
}
if(!boleh){break;}
}
if(boleh){
stack1.pop_back();
for(int i: stack1){
printf("%d ", i);
}
exit(0);
}
}else{
for(int v = 1; v <= N; v ++){
if(AdjMat[u][v] && u != v && !picked[v]){
picked[v] = true;
stack1.push_back(v);
dfs(v, s, k+1);
stack1.pop_back();
picked[v] = false;
}
}
}
}
int main(){
scanf("%d%d", &N, &R);
memset(AdjMat, 0, sizeof(AdjMat));
for(int i = 0; i < R; i ++){
int a, b;
scanf("%d%d", &a, &b);
AdjList[a].push_back(b);
AdjList[b].push_back(a);
AdjMat[a][b] = 1;
AdjMat[b][a] = 1;
}
if(N <= 1000){
for(int i = 1; i <= N; i ++){
stack1.clear();
stack1.push_back(i);
memset(picked, false, sizeof(picked));
dfs(i, i, 0);
}
printf("no");
return 0;
}
memset(visited, 0, sizeof(visited));
for(int i = 1; i <= N; i ++){
queue<int> q;
q.push(i);
vector<int> component;
component.push_back(i);
memset(dist, -1, sizeof(dist));
memset(p, -1, sizeof(p));
dist[i] = 0;
int x = -1;
int y = -1;
int minCycle = N+5;
while(!q.empty()){
int u = q.front(); q.pop();
bool found = false;
for(int v: AdjList[u]){
if(dist[v] == -1){
component.push_back(v);
dist[v] = dist[u]+1;
p[v] = u;
q.push(v);
}else if(v != p[u]){
int temp = dist[u]+dist[v] +1 ;
if(temp < minCycle){
minCycle = temp;
//printf("p[%d]=%d; p[%d]=%d\n", u, p[u], v, p[v]);
//found = true;
x = u;
y = v;
}
}
}
if(found){break;}
}
if(minCycle <= N && minCycle >= 4){
//printf("x=%d y=%d\n", x, y);
vector<int> X;
vector<int> Y;
while(x != -1){
X.push_back(x);
x = p[x];
}
reverse(X.begin(), X.end());
memset(forbidden, false, sizeof(forbidden));
for(int x: X){
forbidden[x] = true;
}
/*
memset(dist, -1, sizeof(dist));
memset(p, -1, sizeof(p));
dist[i] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
for(int v: AdjList[u]){
if(dist[v] == -1 && !forbidden[v]){
component.push_back(v);
dist[v] = dist[u]+1;
p[v] = u;
q.push(v);
}
}
}
*/
while(y != i){
X.push_back(y);
y = p[y];
}
for(int k: X){
printf("%d ", k);
}
return 0;
}
}
printf("no");
return 0;
}
Compilation message
indcyc.cpp: In function 'int main()':
indcyc.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &R);
~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1408 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1085 ms |
1280 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
1408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
1408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
1408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1098 ms |
1920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
1664 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
2304 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
