#include <bits/stdc++.h>
using namespace std;
const int MN = 1005, LG = 12;
int n, m, i, x, y, vis[MN], d[MN], p[MN], sp[MN][LG], t[MN][2], nxt, rev[MN];
pair<int,int> e[MN];
vector<int> adj[MN], ee[MN], eee[MN], tt[MN], ans;
queue<int> q;
set<pair<int,int>> done;
void dfs(int n,int p){
/*printf("%d: ",n);
for(auto v : tt[n])
printf("%d ",v);
printf("\n");*/
t[n][0] = ++nxt; rev[nxt] = n;
sp[n][0] = p;
for(auto v : tt[n])
dfs(v, n);
t[n][1] = nxt;
}
int anc(int x,int y){
if(d[x]<d[y]) swap(x,y);
for(int i=LG-1;i>=0;i--){
if((1<<i)<=d[x]-d[y])
x = sp[x][i];
}
if(x==y) return x;
for(int i=LG-1;i>=0;i--){
if(sp[x][i]!=sp[y][i]){
x=sp[x][i];
y=sp[y][i];
}
}
return sp[x][0];
}
bool solve(int l,int r){
if(done.count({l,r})) return 0;
done.insert({l,r}); int f=0;
if(ee[l][0]<r&&solve(l,ee[l][0])) return 1;
else if(ee[l][0]<r) f=1;
if(eee[r].back()>l&&solve(eee[r].back(),r)) return 1;
else if(eee[r].back()>l) f=1;
int x = anc(rev[l], rev[r]);
if(d[rev[l]]+d[rev[r]]-2*d[x]>=3&&!f){
memset(p,0,sizeof(p));
q.push(rev[l]); p[rev[l]]=-1;
while(q.size()){
x = q.front(); q.pop();
for(auto v : tt[x]){
if(!p[v]){
p[v] = x;
q.push(v);
}
}
if(sp[x][0]&&!p[sp[x][0]]){
p[sp[x][0]] = x;
q.push(sp[x][0]);
}
for(auto v : ee[t[x][0]]){
if((x<=l&&v>=r)||(x>=r&&v<=l)) continue;
if(!p[rev[v]]){
p[rev[v]] = x;
q.push(rev[v]);
}
}
}
x = rev[r];
while(~x){
ans.push_back(x);
x = p[x];
}
return 1;
}
}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=m;i++){
scanf("%d%d",&x,&y);
adj[x].push_back(y);
adj[y].push_back(x);
e[i]={x,y};
}
q.push(1); vis[1]=1;
while(q.size()){
x = q.front(); q.pop();
for(auto v : adj[x]){
if(!vis[v]){
vis[v]=1; d[v]=d[x]+1; p[v]=x;
q.push(v);
}
}
if(p[x]){
adj[p[x]].erase(find(adj[p[x]].begin(),adj[p[x]].end(),x));
adj[x].erase(find(adj[x].begin(),adj[x].end(),p[x]));
}
tt[p[x]].push_back(x);
}
dfs(1,0);
for(int j=1;j<LG;j++){
for(i=1;i<=n;i++)
sp[i][j]=sp[sp[i][j-1]][j-1];
}
for(i=1;i<=n;i++){
for(auto v : adj[rev[i]]){
if(t[v][0]>=i) ee[i].push_back(t[v][0]);
else eee[i].push_back(t[v][0]);
}
}
for(i=1;i<=n;i++){
sort(ee[i].begin(),ee[i].end());
sort(eee[i].begin(),eee[i].end());
}
for(i=1;i<=n;i++){
for(auto v : ee[i]){
if(solve(i,v)) break;
}
if(ans.size()) break;
for(auto v : eee[i]){
if(solve(v,i)) break;
}
if(ans.size()) break;
}
if(ans.size()){
for(auto v : ans) printf("%d ",v);
printf("\n");
}
else printf("no\n");
return 0;
}
Compilation message
indcyc.cpp: In function 'bool solve(int, int)':
indcyc.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
indcyc.cpp: In function 'int main()':
indcyc.cpp:80:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(scanf("%d%d",&n,&m),i=1;i<=m;i++){
~~~~~~~~~~~~~~~~~~~^~~~
indcyc.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
508 KB |
Too short sequence |
| 2 |
Incorrect |
2 ms |
376 KB |
Wrong answer on graph without induced cycle |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Too short sequence |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Too short sequence |
| 2 |
Incorrect |
2 ms |
504 KB |
Wrong answer on graph without induced cycle |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1116 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
