| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 244557 | oolimry | Potemkin cycle (CEOI15_indcyc) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//HAPPY BIRTHDAY!!!
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int depth[1005];
vector<int> adj[1005];
vector<int> paths[1005];
vector<int> p[1005];
vector<ii> backs;
void dfs(int u){
for(int v : adj[u]){
if(depth[v] != 0){
if(depth[v] < depth[u]-1){ ///back edge
int dist = depth[u] - depth[v];
backs.push_back(ii(dist, u));
}
}
else{
depth[v] = depth[u] + 1;
paths[v].push_back(u);
p[v] = u;
dfs(v);
}
}
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m;
for(int i = 0;i < m;i++){
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i = 1;i <= n;i++){
if(depth[i] != 0) continue; ///visited;
backs.clear();
depth[i] = 1;
dfs(i);
sort(backs.begin(), backs.end());
for(ii e : backs){
//cout << e.first << " " << e.second << ":" << endl;
int u = e.second;
int targetDepth = depth[u] - e.first;
//cout << targetDepth << "\n";
vector<int> P;
while(depth[u] != targetDepth){
P.push_back(u);
for(int i = (int) (paths[u].size()-1);i >= 0;i--){
int v = paths[u][i];
//cout << u << " " << v << endl;
if(depth[v] >= targetDepth){
u = v;
break;
}
}
}
P.push_back(u);
if((int) P.size() >= 3){
for(int x : P) cout << x << " ";
return 0;
}
else{
paths[e.second].push_back(u);
}
}
}
cout << "no";
}