Submission #702224

#	Time	Username	Problem	Language	Result	Execution time	Memory
702224		amirhoseinfar1385	Potemkin cycle (CEOI15_indcyc)	C++17	20 / 100	13 ms	2008 KiB

indcyc

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
int par[maxn],vis[maxn],len[maxn];
vector<int>adj[maxn];
int n,m;
vector<int>fb,res,resl,resr;
int had;
void solve(int lena=0){
	if((int)fb.size()==0){
		return ;
	}
	for(auto x:fb){
		len[x]=lena;
		vis[x]=1;
	}
	vector<int>fake;
	for(auto x:fb){
		for(auto y:adj[x]){
			if(vis[y]==1){
				if(len[x]>len[y]){
					continue;
				}
				int now=y;
				while(now>0){
					res.push_back(now);
					//cout<<"res "<<now<<" "<<x<<"\n";
					now=par[now];
				}
				now=x;
				while(now>0){
					resr.push_back(now);
					//cout<<"resr "<<now<<" "<<x<<"\n";
					now=par[now];
				}
				resr.pop_back();
				reverse(resr.begin(),resr.end());
				for(auto x:resr){
					res.push_back(x);
				}	
				return ;
			}
			else{
				vis[y]=1;
				len[y]=lena+1;
				par[y]=x;
				fake.push_back(y);
			}
		}
	}
	fb.swap(fake);
	solve(lena+1);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		for(int i=0;i<=n+1;i++){
			par[i]=vis[i]=len[i]=0;
		}
		fb.clear();
		fb.push_back(i);
		solve();
		if(res.size()>0){
			break;
		}
	}
	if(res.size()==0){
		cout<<"no\n";
	}
	else{
		for(auto x:res){
			cout<<x<<" ";
		}
		cout<<"\n";
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10