相关链接
题目传送门: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; }