제출 #785035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785035		NK_	Potemkin cycle (CEOI15_indcyc)	C++17	10 / 100	15 ms	1296 KiB

indcyc

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

template<class T> using V = vector<T>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	// TIME TO IMPLEMENT FOR 40 MIN TO REALIZE THE IDEA IS WRONG!! 
	// (0-0)

	int N, M; cin >> N >> M;

	V<V<int>> adj(N); for(int e = 0; e < M; e++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	V<int> vis(N, 0), low(N, -1), disc(N, -1); int t = 0;

	V<int> stk = {-1};
	function<void(int, int)> dfs = [&](int u, int p) {
		vis[u] = 1;
		disc[u] = ++t; stk.pb(u);
		int best = -1;
		sort(begin(adj[u]), end(adj[u]), [&](int x, int y) {
			return disc[x] > disc[y];
		});

		for(auto& v : adj[u]) if (v != p) {
			if (vis[v]) {
				// back edge -> cycle
				best = max(best, disc[v]);
			} else {
				low[v] = max(low[u], best);
				dfs(v, u);
			}
		}

		int len = disc[u] - best + 1;
		if (low[u] < best && len >= 4) {
			int x = -1; for(auto& v : adj[u]) if (v != p) {
				if (disc[v] == best) x = v;
			}

			assert(x != -1);

			while(stk.back() != x) { cout << stk.back() + 1 << " "; stk.pop_back(); }
			cout << x + 1 << nl;
			exit(0);
		}
		--t; stk.pop_back();
	};

	dfs(0, -1);

	cout << "no" << nl;

    return (0-0);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 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