#include<bits/stdc++.h>
#define DEBUG false
using namespace std;
vector<vector<int> > g, h;
int n, r;
vector<int> par;
int find(int cur){
if(par[cur] == cur) return cur;
return par[cur] = find(par[cur]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a == b) return;
par[b] = a;
}
vector<vector<int> > l;
vector<vector<pair<int, int> > >el;
void bfs(int m, int u, int v){
vector<int> dist(n, INT_MAX);
vector<int> dpar(n, -1);
dist[u] = 0;
queue<int> q; q.push(u);
while(!q.empty()){
int top = q.front(); q.pop();
for(int ad: g[top]){
if(ad != u && ad != v && (ad == m || (h[ad][m]))) continue;
if(dist[ad] == INT_MAX){
dist[ad] = dist[top]+1;
q.push(ad);
dpar[ad] = top;
}
}
}
assert(dist[v] != INT_MAX);
vector<int> path = {u, m};
int cur = v;
while(cur != u){
path.push_back(cur);
cur = dpar[cur];
}
for(int i = 0; i < path.size(); i++){
for(int j = i+1; j < path.size(); j++){
if(abs(i-j) == 1 || (i == 0 && j == path.size()-1)) continue;
assert(h[path[i]][path[j]] == false);
}
}
assert(path.size() >= 4);
for(int k: path) cout<<k+1<<" ";
cout<<endl;
exit(0);
}
vector<bool> ne;
void rec(vector<int> v, vector<pair<int, int> > e){
if(v.size() < 4) return;
if(DEBUG) cout<<"REC: ";
if(DEBUG) for(int u: v) cout<<u<<" ";
if(DEBUG) cout<<endl;
//reset all the dsu of v
for(int u: v) par[u] = u;
//select main node, and find neighbors
int m = v[0];
for(int u: v){
if(h[u][m]) ne[u] = true;
else ne[u] = false;
}
ne[m] = true;
if(DEBUG) for(int i = 0; i < n; i++) cout<<i<<" : "<<ne[i]<<endl;
for(pair<int, int> ed: e){
if(ne[ed.first] || ne[ed.second]) continue;
merge(ed.first, ed.second);
if(DEBUG) cout<<"MERGE "<<ed.first<<" , "<<ed.second<<endl;
assert(find(ed.first) == find(ed.second));
}
for(int u: v) l[u].clear();
//loop to add all S to G - s - v edges
for(pair<int, int> ed: e){
if(ed.first == m || ed.second == m) continue;
if(ne[ed.first] && !ne[ed.second]){
int t = find(ed.second);
l[t].push_back(ed.first);
if(DEBUG) cout<<"PUSH "<<t<<" "<<ed.first<<endl;
}else if(!ne[ed.first] && ne[ed.second]){
int t = find(ed.first);
l[t].push_back(ed.second);
if(DEBUG) cout<<"PUSH "<<t<<" "<<ed.second<<endl;
}
}
if(DEBUG) cout<<"REACHED"<<endl;
//for each l find
for(int u: v) el[u].clear();
for(int u: v){
if(l[u].size() < 2) continue;
assert(u == find(u));
if(DEBUG) cout<<"DOING for "<<u<<endl;
//do a double loop on all pairs to check if they are adjacent
for(int i = 0; i < l[u].size(); i++){
for(int j = i+1; j < l[u].size(); j++){
if(h[l[u][i]][l[u][j]] == false){
//found an answer, output it somehow
//and then exit
//find shortest path from i to j without having an edge to m
bfs(m, l[u][i], l[u][j]);
assert(false);
}else{
el[u].push_back({l[u][i], l[u][j]});
if(DEBUG) cout<<"PUSH "<<l[u][i]<<" "<<l[u][j]<<endl;
}
}
}
}
if(DEBUG) cout<<"REACHED"<<endl;
vector<int> nel;
vector<pair<int, int> > edl;
for(int u: v){
if(ne[u] && u != m){
nel.push_back(u);
}else if(u != m){
l[find(u)].push_back(u);
}
}
for(pair<int, int>& ed: e){
if(ne[ed.first] == true && ne[ed.second] == false){
el[find(ed.second)].push_back(ed);
}else if(ne[ed.first] == false && ne[ed.second] == true){
el[find(ed.first)].push_back(ed);
}else if(ne[ed.first] && ne[ed.second]){
if(ed.first != m && ed.second != m) {
edl.push_back(ed);
}
}else{
if(DEBUG) cout<<"L : "<<ed.first<<" "<<ed.second<<" "<<ne[ed.first]<<" "<<ne[ed.second]<<endl;
assert(find(ed.first) == find(ed.second));
el[find(ed.first)].push_back(ed);
}
}
if(DEBUG) cout<<"REACHED 1"<<endl;
for(int u: v){
for(int k: l[u]) assert(k != m);
for(auto& k: el[u]) assert(k.first != m && k.second != m);
if(l[u].size() >= 4) rec(l[u], el[u]);
}
for(int k: nel) assert(k != m);
for(auto& k: edl) assert(k.first != m && k.second != m);
rec(nel, edl);
if(DEBUG) cout<<"REACHED 2"<<endl;
}
int main(){
//assert(false);
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>r;
g.resize(n);
h = vector<vector<int> > (n, vector<int>(n));
par.resize(n);
l.resize(n); el.resize(n);
ne.resize(n);
vector<pair<int, int> > elist(r);
for(int i = 0; i < r; i++){
int u, v; cin>>u>>v; u--, v--;
g[u].push_back(v);
g[v].push_back(u);
elist[i] = {u, v};
h[u][v] = 1; h[v][u] = 1;
}
vector<int> v;
for(int i = 0; i < n; i++) v.push_back(i);
rec(v, elist);
assert(false);
cout<<"no"<<endl;
}
Compilation message
indcyc.cpp: In function 'void bfs(int, int, int)':
indcyc.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < path.size(); i++){
~~^~~~~~~~~~~~~
indcyc.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = i+1; j < path.size(); j++){
~~^~~~~~~~~~~~~
indcyc.cpp:51:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(abs(i-j) == 1 || (i == 0 && j == path.size()-1)) continue;
~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'void rec(std::vector<int>, std::vector<std::pair<int, int> >)':
indcyc.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < l[u].size(); i++){
~~^~~~~~~~~~~~~
indcyc.cpp:109:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = i+1; j < l[u].size(); j++){
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
11128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
9904 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
156 ms |
100172 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
