#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int parent[1001];
int find(int i){
if(i==parent[i])return i;
return parent[i]=find(parent[i]);
}
void unite(int i,int j){
i=find(i),j=find(j);
parent[i]=j;
}
vector<int>v[1100];
unordered_set<int>u[1100];
int layer[1100]{};
vector<int>par[1100];
bool visy[1100];
deque<int>resy;
int X,Y;
void dfs(int node){
resy.pb(node);
if(node==Y)return;
visy[node]=1;
for(int j:v[node]){
if(layer[j]!=layer[node])continue;
if(!visy[j]){
dfs(j);
if(resy.back()==Y){
break;
}
}
}
if(resy.back()==node)resy.pop_back();
}
deque<int>findpath(int x,int y){
X=x;Y=y;
dfs(x);
deque<int>ans;
ans.pb(resy.front());
for(int i=1;i<resy.size();i++){
for(int j=0;j<ans.size();j++){
if(u[ans[j]].count(ans[i])){
while(j+1<ans.size())ans.pop_back();
}
}
ans.pb(resy[i]);
}
return ans;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<=n;i++)parent[i]=i;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
v[x].pb(y);
v[y].pb(x);
u[x].insert(y);
u[y].insert(x);
unite(x,y);
}
queue<int>q;
for(int i=1;i<=n;i++){
if(find(i)!=find(0)){
q.push(i);
layer[i]=1;
unite(i,0);
}
}
while(q.size()){
int node=q.front();
q.pop();
for(int j:v[node]){
if(layer[node]<layer[j])par[j].pb(node);
if(!layer[j]){
par[j].pb(node);
layer[j]=layer[node]+1;
q.push(j);
}
}
}
int x=0,y=0,z=0;
for(int i=1;i<=n;i++){
for(int j:par[i]){
for(int k:par[i]){
if(j==k)continue;
if(!u[j].count(k)){
x=i,y=j,z=k;
break;
}
}
if(x)break;
}
if(x)break;
}
if(x){
vector<int>chain1,chain2;
chain1.pb(x);
chain1.pb(y);
chain2.pb(z);
while(!u[chain1.back()].count(chain2.back())){
int ng1=par[chain1.back()][0];
int ng2=par[chain2.back()][0];
if(u[chain1.back()].count(ng2)){
chain2.pb(ng2);
break;
}
if(u[chain2.back()].count(ng1)){
chain1.pb(ng1);
break;
}
chain1.pb(ng1);
chain2.pb(ng2);
}
for(int i=0;i<chain1.size();i++){
cout<<chain1[i]<<' ';
}
for(int i=chain2.size()-1;0<=i;i--){
cout<<chain2[i]<<' ';
}
return 0;
}
for(int i=0;i<=n;i++)parent[i]=i;
for(int i=1;i<=n;i++){
for(int j:v[i]){
if(layer[i]==layer[j])unite(i,j);
}
}
int w=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(j<i||layer[i]!=layer[j]||find(i)!=find(j))continue;
int g1=0,g2=0;
for(int k:par[i]){
if(!u[j].count(k)){
g1=k;
break;
}
}
for(int k:par[j]){
if(!u[i].count(k)){
g2=k;
break;
}
}
if(g1&&g2){
x=i,y=j,w=g1,z=g2;
break;
}
}
if(x)break;
}
if(x){
deque<int>chain1,chain2,chain3;
chain3=findpath(y,x);
chain1.pb(x);
chain1.pb(w);
chain2.pb(y);
chain2.pb(z);
while(!u[chain1.back()].count(chain2.back())){
int ng1=par[chain1.back()][0];
int ng2=par[chain2.back()][0];
if(u[chain1.back()].count(ng2)){
chain2.pb(ng2);
break;
}
if(u[chain2.back()].count(ng1)){
chain1.pb(ng1);
break;
}
chain1.pb(ng1);
chain2.pb(ng2);
}
for(int i=0;i<chain1.size();i++){
cout<<chain1[i]<<' ';
}
for(int i=chain2.size()-1;0<=i;i--){
cout<<chain2[i]<<' ';
}
for(int i=1;i+1<chain3.size();i++){
cout<<chain3[i]<<' ';
}
return 0;
}
cout<<"no";
return 0;
}
Compilation message
indcyc.cpp: In function 'std::deque<int> findpath(int, int)':
indcyc.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i=1;i<resy.size();i++){
| ~^~~~~~~~~~~~
indcyc.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int j=0;j<ans.size();j++){
| ~^~~~~~~~~~~
indcyc.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | while(j+1<ans.size())ans.pop_back();
| ~~~^~~~~~~~~~~
indcyc.cpp: In function 'int main()':
indcyc.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i=0;i<chain1.size();i++){
| ~^~~~~~~~~~~~~~
indcyc.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int i=0;i<chain1.size();i++){
| ~^~~~~~~~~~~~~~
indcyc.cpp:186:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for(int i=1;i+1<chain3.size();i++){
| ~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
592 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
592 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
848 KB |
Output is correct |
| 2 |
Correct |
2 ms |
848 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1104 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1104 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
848 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
25 ms |
4944 KB |
Output is correct |
| 2 |
Correct |
11 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
44 ms |
4944 KB |
Output is correct |
| 4 |
Correct |
18 ms |
2640 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
2640 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
48 ms |
9288 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
