제출 #1262412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262412		EntityPlantt	어르신 집배원 (BOI14_postmen)	C++20	38 / 100	818 ms	31556 KiB

postmen

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

constexpr int N = 5e5;
vector<int> g[N];
int vis[N];
set<int> path, connected;

int dfs(int u) {
	path.insert(u);
	while (!g[u].empty()) {
		int v = g[u].back();
		g[v].erase(find(g[v].begin(), g[v].end(), u));
		if (g[v].empty()) connected.erase(v);
		g[u].pop_back();
		if (g[u].empty()) connected.erase(u);
		if (path.count(v)) {
			path.erase(u);
			cout << u + 1 << ' ';
			return v;
		}
		int r = dfs(v);
		if (r != u) {
			path.erase(u);
			cout << u + 1 << ' ';
			return r;
		}
		else cout << u + 1 << '\n';
	}
	return -1;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int a, b;
		cin >> a >> b;
		g[--a].push_back(--b);
		g[b].push_back(a);
	}
	for (int i = 0; i < n; i++) if (!g[i].empty()) connected.insert(i);
	while (!connected.empty()) dfs(*connected.begin());
}

• Subtask 1: 38 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45