Submission #1222168

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
	bool visited = false;
	vector<int> edges;
};

using Graph = vector<Node>;

inline int CanMove(const Graph &g, int node)
{
	for (int next : g[node].edges) {
		if (!g[next].visited) {
			return next;
		}
	}
	return -1;
}

vector<int> FindPath(Graph &g)
{
	vector<int> path;
	int node = 0;

	for (unsigned i = 1; i < g.size(); ++i) {
		if (g[i].edges.size() < g[node].edges.size()) {
			node = i;
		}
	}

	do {
		g[node].visited = true;
		path.push_back(node);
		node = CanMove(g, node);
	} while (node != -1);
	return path;
}

int main()
{
	int n, m;
	cin >> n >> m;

	Graph graph(n);
	while (m--) {
		int x, y;
		cin >> x >> y;
		graph[x - 1].edges.push_back(y - 1);
		graph[y - 1].edges.push_back(x - 1);
	}

	auto path = FindPath(graph);
	cout << path.size() << "\n";

	for (int node : path) {
		cout << node + 1 << " ";
	}
	cout << "\n";

	return 0;
}

Submission Info

Judge Result