【AtCoder】[Grand Contest 013 B] Hamiltonish Path

相关链接

题目传送门:http://agc013.contest.atcoder.jp/tasks/agc013_b

解题报告

最开始想用$DFS$树来搞
然而$Corner \ Case$太多了,写不动啊_(:з」∠)_

最后还是看了题解
题解是使用的调整算法
如果某个端点还可以走,那就走进去
因为每条边至多访问两遍,每个点至多访问一次
所以复杂度是:$O(n + m)$的

Code

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

const int N = 100009;
const int M = N << 1;

int n, m, head[N], nxt[M], to[M], vis[N];
deque<int> ans;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; 
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif	
	n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		AddEdge(u, v);
		if (i == 1) {
			ans.push_back(u);
			ans.push_back(v);
			vis[u] = vis[v] = 1;
		}
	}
	for (int mk = 1; mk; ) {
		mk = 0;
		for (int i = head[ans.front()]; i; i = nxt[i]) {
			if (!vis[to[i]]) {
				mk = 1;
				ans.push_front(to[i]);
				vis[to[i]] = 1;
				break;
			}
		}
	}
	for (int mk = 1; mk; ) {
		mk = 0;
		for (int i = head[ans.back()]; i; i = nxt[i]) {
			if (!vis[to[i]]) {
				mk = 1;
				ans.push_back(to[i]);
				vis[to[i]] = 1;
				break;
			}
		}
	}
	cout<<ans.size()<<endl;
	for (; !ans.empty(); ans.pop_front()) {
		printf("%d ", ans.front());
	}
	return 0;
}