Submission #1222183


Source Code Expand

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {
	int n, m;
	vector<int> v[100000];
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	deque<int> d;
	bool visited[100000] = {};
	for (int i = 0; i < n; i++) {
		if (!v[i].empty()) {
			d.push_back(i);
			visited[i] = true;
			break;
		}
	}
	while (true) {
		bool updated = false;
		int a = d.back();
		for (int i = 0; i < v[a].size(); i++) {
			int b = v[a][i];
			if (!visited[b]) {
				d.push_back(b);
				visited[b] = true;
				updated = true;
				break;
			}
		}
		if (!updated) {
			break;
		}
	}
	while (true) {
		bool updated = false;
		int a = d.front();
		for (int i = 0; i < v[a].size(); i++) {
			int b = v[a][i];
			if (!visited[b]) {
				d.push_front(b);
				visited[b] = true;
				updated = true;
				break;
			}
		}
		if (!updated) {
			break;
		}
	}
	cout << d.size() << endl;
	for (auto i = begin(d); i != end(d); i++) {
		if (i != begin(d)) cout << ' ';
		cout << *i + 1;
	}
	cout << endl;
	return 0;
}

Submission Info

Submission Time
Task B - Hamiltonish Path
User remin
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1159 Byte
Status AC
Exec Time 86 ms
Memory 6784 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 19
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 2688 KB
sample_02.txt AC 2 ms 2688 KB
sample_03.txt AC 2 ms 2688 KB
subtask_1_01.txt AC 66 ms 4864 KB
subtask_1_02.txt AC 17 ms 3200 KB
subtask_1_03.txt AC 60 ms 4864 KB
subtask_1_04.txt AC 69 ms 4736 KB
subtask_1_05.txt AC 69 ms 4736 KB
subtask_1_06.txt AC 69 ms 4736 KB
subtask_1_07.txt AC 72 ms 5888 KB
subtask_1_08.txt AC 74 ms 5888 KB
subtask_1_09.txt AC 86 ms 6784 KB
subtask_1_10.txt AC 22 ms 3328 KB
subtask_1_11.txt AC 26 ms 3456 KB
subtask_1_12.txt AC 2 ms 2688 KB
subtask_1_13.txt AC 2 ms 2688 KB