walking-the-approximate-longest-path_manhlx_300695

walking-the-approximate-longest-path_manhlx_300695.cpp

#include <bits/stdc++.h>
// #include <iostream>
// #include <cstdio>
// #include <cstring>
// #include <cmath>
// #include <algorithm>
// #include <stack>
// #include <queue>
// #include <set>
// #include <map>

using namespace std;

const int BASE = 1e9 + 7;
const int BIGNUM = 1e9;
const int MAXN = 1e5 + 10;

int n, m, counter, last_visited, num;
vector<int> graph[MAXN], save;
vector<pair<int, int> > edges;
int visit[MAXN], parent[MAXN];
int number[MAXN];

void init() {

}

void read_input() {

	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	for(int i = 1; i <= n; i++) {
		edges.clear();
		for(int j = 0; j < graph[i].size(); j++) {
			int t = graph[i][j];
			edges.push_back(make_pair(graph[t].size(), t));
		}
		sort(edges.begin(), edges.end());
		graph[i].clear();
		for(int j = 0; j < edges.size(); j++) {
			graph[i].push_back(edges[j].second);
		}
	}
	
}

void DFS(int u) {

	visit[u] = num;
	last_visited = u;
	counter++;

	int v = -1, s = 1000000;
	for(int i = 0; i < graph[u].size(); i++) {
		int t = graph[u][i];
		number[t]--;
		if (visit[t] != num && number[t] < s) {
			v = t;
			s = number[t];
		}
	}

	if (v != -1) {
		parent[v] = u;
		DFS(v);
	}
}

void trace_path() {

	save.clear();
	while (last_visited != 0) {
		save.push_back(last_visited);
		last_visited = parent[last_visited];
	}
}

void solve() {

	// finding vertex with minimum degree

	edges.clear();
	for(int i = 1; i <= n; i++) {
		if (graph[i].size() > 0) {
			edges.push_back(make_pair(graph[i].size(), i));
		}	
	}

	sort(edges.begin(), edges.end());

	memset(parent, 0, sizeof(parent));
	memset(visit, 0, sizeof(visit));
	num = 0;

	int result = -1;
	for(int ii = 0; ii < edges.size(); ii++) {
		int i = edges[ii].second;
		if (result == n) {
			break;
		}
		if (graph[i].size() > 0) {
			for(int j = 1; j <= n; j++) {
				number[j] = graph[j].size();
			}
			num++;
			counter = 0;
			last_visited = 0;
			parent[i] = 0;
			DFS(i);
			if (counter > result) {
				result = counter;
				trace_path();
			}
		}
		if (ii > 8000) {
			break;
		}
	}

	printf("%d\n", result);
	for(int i = 0; i < result; i++) {
		printf("%d ", save[i]);
	}
	printf("\n");
}

void destroy() {


}

void execute() {

	init();

	int test = 1;
	// scanf("%d\n", &test);
	for(int i = 1; i <= test; i++) {
		read_input();
		solve();
		destroy();
	}

}

int main() {

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	execute();

	return 0;
}