#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repr(i,a,b) for(int i=(a);i>=(b);i--)
#ifdef LOCAL
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...) 1
#endif
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int n,m;
int grp[1010],gc;
int cnt[1010];
bool chk[1010];
vi adj[1010];
void dfs(int u) {
grp[u]=gc;
for(auto& it:adj[u])if(!grp[it]&&(!chk[u]||!chk[it]))dfs(it);
}
void go(int a,int b) {
vector<int> d(n+1,-1),par(n+1);
queue<int> q;
d[b]=0;q.push(b);
while(!q.empty()) {
int u=q.front();q.pop();
if(chk[u]&&u!=b)continue;
for(auto& it:adj[u]) {
if(d[it]!=-1||(chk[u]&&chk[it]))continue;
d[it]=d[u]+1;
par[it]=u;
q.push(it);
}
}
for(auto& it:adj[b]) {
if(!chk[it])continue;
d[it]=0;
}
int e=-1;
for(auto& it:adj[a]) if(d[it]>0) e=it;
vi ans;
while(e!=b)ans.pb(e),e=par[e];
ans.pb(b);ans.pb(a);
for(auto& it:ans)printf("%d ",it);
}
int main() {
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++) {
int u,v;
scanf("%d%d",&u,&v);
adj[u].pb(v);
adj[v].pb(u);
}
for(i=1;i<=n;i++) {
mset(grp,0);gc=0;
chk[i]=true;
for(auto& it:adj[i])chk[it]=true;
for(auto& it:adj[i])if(!grp[it]) {
gc++;
dfs(it);
}
for(j=1;j<=gc;j++)cnt[j]=0;
for(auto& it:adj[i])cnt[grp[it]]++;
for(auto& it:adj[i]){
int c=0;
for(auto& jt:adj[it]) {
if(chk[jt]&&grp[it]==grp[jt])c++;
}
if(c!=cnt[grp[it]]-1) {
go(i,it);
return 0;
}
}
chk[i]=false;
for(auto& it:adj[i])chk[it]=false;
}
puts("no");
return 0;
}
Compilation message
indcyc.cpp: In function 'int main()':
indcyc.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
indcyc.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Execution timed out |
1122 ms |
525772 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Execution timed out |
1114 ms |
525984 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Execution timed out |
1120 ms |
525932 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1127 ms |
525900 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1123 ms |
526468 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1121 ms |
526168 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
1272 KB |
Output is correct |
2 |
Correct |
260 ms |
1272 KB |
Output is correct |
3 |
Execution timed out |
1124 ms |
526664 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |