相关链接
题目传送门：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;
}
哇塞，居然是沙发？留个名
I’m very happy to discover this great site.
I want to to thank you for ones time for this particularly wonderful
read!! I definitely loved every bit of it and I have you saved to
fav to look at new information in your web site.
Hi! This is my 1st comment here so I just wanted to give
a quick shout out and tell you I really enjoy reading your articles.
Can you recommend any other blogs/websites/forums that deal with the same topics?
Thank you!
Wonderful website you have here but I was wondering if you knew of any user discussion forums that cover the same topics talked about here?
I’d really love to be a part of group where I can get suggestions from other experienced
individuals that share the same interest. If you have any recommendations, please let
me know. Bless you!
Thanks for sharing your thoughts. I really appreciate
your efforts and I will be waiting for your next write ups thank you once again.
I used to be able to find good information from your blog articles.
I’m curious to find out what blog platform you have been utilizing?
I’m having some small security problems with
my latest site and I would like to find something more
risk-free. Do you have any suggestions?
I blog frequently and I really thank you for your information. This great article has really peaked my interest.
I am going to take a note of your site and keep checking for new information about once a week.
I opted in for your RSS feed as well.
Pretty! This was an incredibly wonderful post. Many
thanks for providing this information.
I visited multiple blogs except the audio feature for audio songs present
at this website is really superb.
Saved as a favorite, I love your site!
Write more, thats all I have to say. Literally, it
seems as though you relied on the video to make your point.
You clearly know what youre talking about, why throw away your intelligence
on just posting videos to your site when you could be giving us
something informative to read?
I relish, result in I found exactly what I was having a look for. You’ve ended my four day lengthy hunt! God Bless you man. Have a great day. Bye
hello there and thank you for your information – I’ve definitely picked up something new from right here.
I did however expertise several technical points using this
website, as I experienced to reload the site many times previous to I could get
it to load correctly. I had been wondering if your hosting
is OK? Not that I am complaining, but sluggish loading instances times will very frequently affect your placement in google and can damage your high
quality score if advertising and marketing with Adwords.
Anyway I’m adding this RSS to my e-mail and
could look out for a lot more of your respective exciting content.
Make sure you update this again soon.
Awesome! Its actually amazing piece of writing, I have
got much clear idea concerning from this post.
I have been surfing online greater than 3 hours these days, but I never
found any attention-grabbing article like yours.
It’s lovely value enough for me. In my view, if all site
owners and bloggers made just right content as you did, the internet will likely be a lot more useful than ever before.
I always used to study article in news papers but now as I am a user of net thus from now I am using net for articles or reviews,
thanks to web.
I really like it whenever people get together and share opinions.
Great website, stick with it!
An interesting discussion is worth comment. I think that you ought to write more on this topic, it might
not be a taboo subject but usually people do not speak about these topics.
To the next! Many thanks!!
I regard something really special in this website.
Awesome post.Much thanks again. Keep writing.