Submission #73693

#	Time	Username	Problem	Language	Result	Execution time	Memory
73693		arman_ferdous	Potemkin cycle (CEOI15_indcyc)	C++17	70 / 100	1073 ms	6488 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
vector<int> g[N];

int n, m, par[N];
int bfs(int s, int t, int del) {
	par[s] = del;
	par[del] = 0;

	queue<int> q; q.push(s);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int v : g[u]) if(par[v] == -1) {
			par[v] = u; q.push(v);
		}
	} return par[t] != -1;
}

vector<int> soln;
int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		int u, v; scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int u = 1; u <= n; u++)
		sort(g[u].begin(),g[u].end());

	for(int x = 1; x <= n; x++) {
		for(int u : g[x]) for(int v : g[x]) {
			if(u != v && binary_search(g[u].begin(),g[u].end(),v) == false) {
				fill(par,par+n+1,-1);
				for(int i : g[x]) if(i != v && i != u) par[i] = 0;
				if(bfs(u,v,x)) {
					int cur = v;
					while(par[cur]) {
						soln.push_back(cur);
						cur = par[cur];
					} soln.push_back(cur);
					int sz = soln.size();
					for(int i = sz - 1; i >= 0; i--)
						printf("%d ", soln[i]);
					return 0;
				}
			}
		}
	} puts("no");
	return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~

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