#include<bits/stdc++.h>
#define ll long long
using namespace std;
int vis[1009][1009],dep[1009];
vector<int>v[1009][1009],vv[1009];
vector<pair<int,int> >p;
int cn[1009][1009];
int n,m,d;
vector<int>c;
void checkmn(int x,int par)
{
int mxd=0;
for(int i=0;i<v[par][x].size();i++)
{
mxd=max(mxd,dep[v[par][x][i]]);
}
for(int i=mxd;i<c.size()-1;i++)
{
if(cn[c[i]][c[i+1]]==0)
{
return;
}
}
for(int i=mxd;i<c.size();i++)
{
cout<<c[i]+1<<" ";
}
exit(0);
}
void dfs(int x,int par)
{
//cout<<x<<" "<<par<<"\n";
dep[x]=d;
d++;
vis[par][x]=1;
c.push_back(x);
for(int i=0;i<v[par][x].size();i++)
{
int y=v[par][x][i];
//if(vis[x][y])continue;
if(dep[y]!=-1)
{
checkmn(x,par);
}
else dfs(y,x);
}
dep[x]=-1;
d--;
c.pop_back();
}
int main()
{
memset(dep,-1,sizeof(dep));
cin>>n>>m;
int x,y;
for(int i=0;i<m;i++)
{
cin>>x>>y;
x--;y--;
p.push_back({x,y});
cn[x][y]=1;
cn[y][x]=1;
vv[x].push_back(y);
vv[y].push_back(x);
}
for(int i=0;i<m;i++)
{
x=p[i].first;
y=p[i].second;
//cout<<x<<" "<<y<<": ";
for(int j=0;j<vv[y].size();j++)
{
if(vv[y][j]==x)continue;
if(cn[vv[y][j]][x])continue;
v[x][y].push_back(vv[y][j]);
// cout<<v[x][y].back()<<" ";
}
swap(x,y);
//cout<<"\n";
//cout<<x<<" "<<y<<": ";
for(int j=0;j<vv[y].size();j++)
{
if(vv[y][j]==x)continue;
if(cn[vv[y][j]][x])continue;
v[x][y].push_back(vv[y][j]);
// cout<<v[x][y].back()<<" ";
}
// cout<<"\n";
}
d=1;
for(int i=0;i<m;i++)
{
x=p[i].first;
y=p[i].second;
c.clear();
if(vis[x][y]==0)
{
dep[x]=0;
c.push_back(x);
dfs(y,x);
c.pop_back();
dep[x]=-1;
}
swap(x,y);
c.clear();
//if(vis[x][y]==0)
//{
dep[x]=0;
c.push_back(x);
dfs(y,x);
c.pop_back();
dep[x]=-1;
//}
}
cout<<"no";
}
Compilation message
indcyc.cpp: In function 'void checkmn(int, int)':
indcyc.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[par][x].size();i++)
~^~~~~~~~~~~~~~~~~
indcyc.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=mxd;i<c.size()-1;i++)
~^~~~~~~~~~~
indcyc.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=mxd;i<c.size();i++)
~^~~~~~~~~
indcyc.cpp: In function 'void dfs(int, int)':
indcyc.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[par][x].size();i++)
~^~~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vv[y].size();j++)
~^~~~~~~~~~~~~
indcyc.cpp:81:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vv[y].size();j++)
~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
24312 KB |
Output is correct |
2 |
Correct |
24 ms |
24312 KB |
Output is correct |
3 |
Correct |
25 ms |
24312 KB |
Output is correct |
4 |
Correct |
24 ms |
24312 KB |
Output is correct |
5 |
Correct |
24 ms |
24184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
24280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
24244 KB |
Output is correct |
2 |
Correct |
24 ms |
24312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
24696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
27 ms |
24956 KB |
Wrong adjacency |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1078 ms |
26404 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
27640 KB |
Output is correct |
2 |
Correct |
250 ms |
28296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1068 ms |
45172 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
213 ms |
75260 KB |
Output is correct |
2 |
Execution timed out |
1086 ms |
81020 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
484 ms |
29956 KB |
Output is correct |
2 |
Correct |
488 ms |
29544 KB |
Output is correct |
3 |
Correct |
483 ms |
111924 KB |
Output is correct |
4 |
Execution timed out |
1094 ms |
115696 KB |
Time limit exceeded |