#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
const int N = 1003, R = 100005;
int n, r;
vector<int>adj[N];
vector<int>ans;
vector<int > backedges[N];
bool connected[N][N];
short vis[N];
const int unvisited = -1;
const int visited = 0;
const int past = 1;
void dfs(int u, int parent, int d){
vis[u] = visited;
for(auto v : adj[u]){
if(v == parent)continue;
if(vis[v] == unvisited){
dfs(v, u, d + 1);
}else if(vis[v] == past)continue;
else{
backedges[u].pb(v);
}
}
vis[u] = past;
}
bool isOpS[N], banned[N];
int anterior[N];
int correspondingS[N];
int distancia[N];
short visBfs[N];
bool try_solve(int t, int s){
return true;
}
bool isBackedge[N];
bool try_solve(int t){
if(backedges[t].empty())return false;
//cout << "t = " << t << endl;
priority_queue<pair<int, pair<int, int > > >pq; // dist, nodo anterior
vector<int>pisados;
for(auto s : backedges[t]){
isBackedge[s] = true;
}
for(auto start : adj[t]){
if(isBackedge[start])continue;
pq.push({1, {start, t}});
//cout << "starting at " << start << endl;
pisados.pb(start);
visBfs[start] = 1;
}
for(auto s : backedges[t]){
isBackedge[s] = false;
}
distancia[t] = 0;
/// Hay que banear a S?
pisados.pb(t);
visBfs[t] = 1;
int found = -1;
while(!pq.empty()){
auto nxt = pq.top();
int d = min(nxt.ff, 3);
int u = nxt.ss.ff;
anterior[u] = nxt.ss.ss;
distancia[u] = d;
pq.pop();
for(auto v : adj[u]){
if(visBfs[v])continue;
if(min(d + 1, 3) > distancia[v]){
pq.push({min(d + 1, 3), {v, u}});
visBfs[v] = 1;
pisados.pb(v);
}
}
}
int sFound = -1;
for(auto s : backedges[t]){
//cout << "backedge " << s << endl;
if(distancia[s] >=3 ){
found = s;
break;
}
}
if(found != -1){
//cout << "camino encontrado" << endl;
//cout << "t: " << t << endl;
vector<int>camino;
camino.push_back(found);
//cout << "agg " << camino.back()<< endl;
while(camino.back() != t){
camino.push_back(anterior[camino.back()]);
//cout << "agg " << camino.back()<< endl;
}
for(int i = 0 ; i < camino.size()-1 ; i ++){
int addin = camino[i];
for(int j = 0 ; j < ans.size() ; j ++){
if(connected[addin][ans[j]]){
int eliminamos = ans.size() - (j + 1);
for(int x = 0 ; x < eliminamos ; x ++)ans.pop_back();
break;
}
}
//cout << "cam " << addin << endl;
ans.pb(addin);
//for(auto i : ans)cout << i << " " ;
//cout << endl;
}
ans.pb(t);
return true;
}
for(auto i : pisados){
visBfs[i] = 0;
distancia[i] = 0;
}
return false;
}
bool respond(int u, int parent, int deepest){
vis[u] = visited;
if(try_solve(u))return true;
for(auto v : adj[u]){
if(parent == v)continue;
if(vis[v] == unvisited && respond(v, u, deepest))return true;
}
vis[u] = past;
return false;
}
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(NULL);
cin >> n >> r;
memset(connected, false, sizeof connected);
for(int i = 0 ; i < r ; i ++){
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
connected[u][v] = true;
connected[v][u] = true;
}
for(int i = 1 ; i <= n ; i ++)vis[i] = unvisited;
dfs(1, -1, 0);
for(int i = 1 ; i <= n ; i ++)vis[i] = unvisited;
for(int i = 1 ; i <= n ; i ++)visBfs[i] = 0;
memset(isBackedge, false, sizeof isBackedge);
if(!respond(1, -1, -10))cout << "no";
else{
for(auto i : ans)cout << i << " ";
}
}
Compilation message
indcyc.cpp: In function 'bool try_solve(int)':
indcyc.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0 ; i < camino.size()-1 ; i ++){
| ~~^~~~~~~~~~~~~~~~~
indcyc.cpp:109:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int j = 0 ; j < ans.size() ; j ++){
| ~~^~~~~~~~~~~~
indcyc.cpp:85:9: warning: unused variable 'sFound' [-Wunused-variable]
85 | int sFound = -1;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1624 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1372 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1372 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1532 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1628 KB |
Wrong answer on graph without induced cycle |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1372 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
2728 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1884 KB |
Wrong adjacency |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
3676 KB |
Expected integer, but "no" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
