| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 115845 | rajarshi_basu | 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.
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
using namespace std;
const int INF = 1e9+10;
const int MAXN = 1000+10;
int n,m;
bool mat[MAXN][MAXN];
bool vis[MAXN][MAXN];
stack<ii> cyc;
set<int> allnode;
bool done = 0;
inline bool isok(int a,int b,int c){
return (!(mat[a][b] and mat[b][c] and mat[a][c])) and mat[b][c];
}
void dfs1(ii node){
if(done)return;
cyc.push(node);
//cout << node.ff << " " << node.ss << endl;
if(vis[node.ff][node.ss]){
// we got our cycle
allnode.insert(node.ff);
allnode.insert(node.ss);
cyc.pop();
while(cyc.size()>0){
ii x = cyc.top();cyc.pop();
allnode.insert(x.ff);
allnode.insert(x.ss);
if(x == node)break;
}
done = 1;
return;
}
vis[node.ff][node.ss] = 1;
FOR(nxt,n){
if(nxt == node.ff)continue;
if(isok(node.ff,node.ss,nxt)){
// this is a valid edge;
dfs1({node.ss,nxt});
if(done)return;
}
}
if(cyc.size()>0)cyc.pop();
}
bool impNode[MAXN];
bool vis2[MAXN];
stack<int> st;
vector<int> cc;
void dfs2(int node,int p = -1){
if(done)return;
st.push(node);
if(vis2[node]){
st.pop();
while(1){
int x = st.top();st.pop();
cc.pb(x);
if(x == node)break;
}
done = 1;
return;
}
vis2[node] = 1;
FOR(i,n){
if(node == i)continue;
if(!mat[i][node])continue;
if(!impNode[i])continue;
if(p == i)continue;
dfs2(i,node);
}
if(st.size()>0)st.pop();
}
int main(){
cin >> n >> m;
FOR(i,m){
int a,b;
cin >> a >> b;
a--;b--;
mat[a][b] = mat[b][a] = 1;
}
// input done
FOR(i,n){
dfs1({i,i});
}
if(!done){
cout << "no1" << endl;
return 0;
}
int x;
for(auto e:allnode){
impNode[e] = 1;
x = e;
}
for(auto e:allnode){
//cout << e << endl;
}
done = 0;
dfs2(x);
if(cc.empty()){
cout << "no" << endl;
}else{
for(auto e:cc){
cout << e+1 << " ";
}
cout << endl;
}
return 0;
}#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
using namespace std;
const int INF = 1e9+10;
const int MAXN = 1000+10;
int n,m;
bool mat[MAXN][MAXN];
bool vis[MAXN][MAXN];
stack<ii> cyc;
set<int> allnode;
bool done = 0;
inline bool isok(int a,int b,int c){
return (!(mat[a][b] and mat[b][c] and mat[a][c])) and mat[b][c];
}
void dfs1(ii node){
if(done)return;
cyc.push(node);
//cout << node.ff << " " << node.ss << endl;
if(vis[node.ff][node.ss]){
// we got our cycle
allnode.insert(node.ff);
allnode.insert(node.ss);
cyc.pop();
while(cyc.size()>0){
ii x = cyc.top();cyc.pop();
allnode.insert(x.ff);
allnode.insert(x.ss);
if(x == node)break;
}
done = 1;
return;
}
vis[node.ff][node.ss] = 1;
FOR(nxt,n){
if(nxt == node.ff)continue;
if(isok(node.ff,node.ss,nxt)){
// this is a valid edge;
dfs1({node.ss,nxt});
if(done)return;
}
}
if(cyc.size()>0)cyc.pop();
}
bool impNode[MAXN];
bool vis2[MAXN];
stack<int> st;
vector<int> cc;
void dfs2(int node,int p = -1){
if(done)return;
st.push(node);
if(vis2[node]){
st.pop();
while(1){
int x = st.top();st.pop();
cc.pb(x);
if(x == node)break;
}
done = 1;
return;
}
vis2[node] = 1;
FOR(i,n){
if(node == i)continue;
if(!mat[i][node])continue;
if(!impNode[i])continue;
if(p == i)continue;
dfs2(i,node);
}
if(st.size()>0)st.pop();
}
int main(){
cin >> n >> m;
FOR(i,m){
int a,b;
cin >> a >> b;
a--;b--;
mat[a][b] = mat[b][a] = 1;
}
// input done
FOR(i,n){
dfs1({i,i});
}
if(!done){
cout << "no1" << endl;
return 0;
}
int x;
for(auto e:allnode){
impNode[e] = 1;
x = e;
}
for(auto e:allnode){
//cout << e << endl;
}
done = 0;
dfs2(x);
if(cc.empty()){
cout << "no" << endl;
}else{
for(auto e:cc){
cout << e+1 << " ";
}
cout << endl;
}
return 0;
}
#include <complex>
#include <stack>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
using namespace std;
const int INF = 1e9+10;
const int MAXN = 1000+10;
int n,m;
bool mat[MAXN][MAXN];
bool vis[MAXN][MAXN];
stack<ii> cyc;
set<int> allnode;
bool done = 0;
inline bool isok(int a,int b,int c){
return (!(mat[a][b] and mat[b][c] and mat[a][c])) and mat[b][c];
}
void dfs1(ii node){
if(done)return;
cyc.push(node);
//cout << node.ff << " " << node.ss << endl;
if(vis[node.ff][node.ss]){
// we got our cycle
allnode.insert(node.ff);
allnode.insert(node.ss);
cyc.pop();
while(cyc.size()>0){
ii x = cyc.top();cyc.pop();
allnode.insert(x.ff);
allnode.insert(x.ss);
if(x == node)break;
}
done = 1;
return;
}
vis[node.ff][node.ss] = 1;
FOR(nxt,n){
if(nxt == node.ff)continue;
if(isok(node.ff,node.ss,nxt)){
// this is a valid edge;
dfs1({node.ss,nxt});
if(done)return;
}
}
if(cyc.size()>0)cyc.pop();
}
bool impNode[MAXN];
bool vis2[MAXN];
stack<int> st;
vector<int> cc;
void dfs2(int node,int p = -1){
if(done)return;
st.push(node);
if(vis2[node]){
st.pop();
while(1){
int x = st.top();st.pop();
cc.pb(x);
if(x == node)break;
}
done = 1;
return;
}
vis2[node] = 1;
FOR(i,n){
if(node == i)continue;
if(!mat[i][node])continue;
if(!impNode[i])continue;
if(p == i)continue;
dfs2(i,node);
}
if(st.size()>0)st.pop();
}
int main(){
cin >> n >> m;
FOR(i,m){
int a,b;
cin >> a >> b;
a--;b--;
mat[a][b] = mat[b][a] = 1;
}
// input done
FOR(i,n){
dfs1({i,i});
}
if(!done){
cout << "no" << endl;
return 0;
}
int x;
for(auto e:allnode){
impNode[e] = 1;
x = e;
}
for(auto e:allnode){
//cout << e << endl;
}
done = 0;
dfs2(x);
if(cc.empty()){
cout << "no" << endl;
}else{
for(auto e:cc){
cout << e+1 << " ";
}
cout << endl;
}
return 0;
}