Submission #1501143

---

Source Code Expand

#include <bits/stdc++.h>
#define pb push_back

using namespace std;
const int maxn = 1e5 + 7;

vector<int> G[maxn];
int pi[maxn];
int dep[maxn];
bool vis[maxn];
int lf;


void dfs(int x,int h) {
	int ch = 0; dep[x] = h;
	
	for (int j = 0; j < G[x].size(); j++) {
		int z = G[x][j];
		if (pi[z] > -2) continue;
		pi[z] = x; ch++;
		dfs(z,h+1);
	}

	if (ch == 0) lf = x;
}



vector<int> p;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int n,m; cin>>n>>m;

	for (int i = 1; i <= n; i++) {
		pi[i] = -2; dep[i] = 0; vis[i] = false;
	}

	for (int i = 1; i <= m; i++) {
		int x,y; cin>>x>>y;
		G[x].pb(y); G[y].pb(x);
	}
	
	pi[1] = -1;
	dfs(1,0);	

	int cur = lf; int maxh = 0;
	
	p.clear();

	while (true) {
		while (dep[cur] >= maxh) {
			//cout<<cur<<" : "<<pi[cur]<<endl;
			vis[cur] = true; p.pb(cur);
			if (pi[cur] < 0 || vis[pi[cur]]) break;
			cur = pi[cur];
		}
		maxh = dep[cur] + 1; bool ok = false;
		for (int j = 0; j < G[cur].size(); j++) {
			if (!vis[ G[cur][j] ]) { cur = G[cur][j]; ok = true; break; }
		}

		if (!ok) break;
	}

	cout<<p.size()<<endl;
	for (int i = 0; i < p.size(); i++) {
		cout<<p[i]<<" ";
	}
	cout<<endl;

}

Submission Info

Judge Result