Walking the Approximate Longest Path

                            Solution in C :

In  C++  :







#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

#define SIZE(x) (int((x).size()))
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define repd(i,r,l) for (int i=(r); i>=(l); i--)
#define rept(i,c) for (typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

#ifndef ONLINE_JUDGE
#define debug(x) { cerr<<#x<<" = "<<(x)<<endl; }
#else
#define debug(x) {}
#endif

#define maxn 10010

vector<int> e[maxn];
int vis[maxn], seq[2*maxn], ans[2*maxn];

void lemon()
{
	int n,m; scanf("%d%d",&n,&m);
	rep(i,1,m)
	{
		int x,y; scanf("%d%d",&x,&y);
		e[x].push_back(y); e[y].push_back(x);
	}
	
	int maxv=0;
	
	rep(iter,1,10)
	{
		memset(vis,0,sizeof vis);
		seq[1+maxn]=rand()%n+1; vis[seq[1+maxn]]=1;
		int beg = 1, all=1, last=seq[1+maxn], noprogress=0;
		while (noprogress<200)
		{
			int k=rand()%e[last].size();
			k=e[last][k];
			if (!vis[k])
			{
				vis[k]=1; all++; seq[all+maxn]=k; last=k;
				noprogress=0;
			}
			else
			{
				int where;
				rep(i,beg,all) if (seq[i+maxn]==k) { where=i; break; }
				reverse(seq+where+maxn+1,seq+all+maxn+1);
				last=seq[all+maxn];
				noprogress++;
			}
		}
		last=seq[1+maxn], noprogress=0;
		while (noprogress<200 && all-beg+1<n)
		{
			int k=rand()%e[last].size();
			k=e[last][k];
			if (!vis[k])
			{
				vis[k]=1; beg--; seq[beg+maxn]=k; last=k;
				noprogress=0;
			}
			else
			{
				int where;
				rep(i,beg,all) if (seq[i+maxn]==k) { where=i; break; }
				reverse(seq+beg+maxn,seq+where+maxn);
				last=seq[beg+maxn];
				noprogress++;
			}
		}
		if (all-beg+1>maxv) 
		{
			maxv=all-beg+1; int c=0;
			rep(i,beg,all)
			{
				c++; ans[c]=seq[i+maxn];
			}
		}
	}
	
	printf("%d\n",maxv);
	rep(i,1,maxv) printf("%d ",ans[i]); printf("\n");
}

int main()
{
	srand(time(0));
	ios::sync_with_stdio(true);
	#ifndef ONLINE_JUDGE
	//	freopen("5.in","r",stdin);
	#endif
	lemon();
	return 0;
}









In   Java  ;







import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int n1=0;
        int n2=0;
        ArrayList<ArrayList<Integer>> nodeConn = new ArrayList<ArrayList<Integer>>();
        int[] nodeLen = new int[n];
        for (int i=0; i<n; i++){
            nodeConn.add(new ArrayList<Integer>());
        }
        for (int i=0; i<m; i++){
            n1 = in.nextInt()-1;
            n2 = in.nextInt()-1;
            nodeConn.get(n1).add(n2);
            nodeLen[n1]++;
            nodeConn.get(n2).add(n1);
            nodeLen[n2]++;
        }
        int min=0;
        for (int i=0; i<n; i++){
            //System.out.print((i+1) + " "+ nodeLen[i]+" ");
            if(nodeLen[i]<nodeLen[min])
                min=i;
            //System.out.println(min+1);
        }
        ArrayList<Integer> temp = new ArrayList<Integer>();
        int currNode = 0;
        int newMin = 0;
        int count = 0;
        int[] path = new int[n];
        while(nodeLen[min]!=0&&count<=n){
            path[count]=min+1;
            temp = nodeConn.get(min);
            newMin=temp.get(0);
            for(int i=0; i<temp.size(); i++){
                currNode = temp.get(i);
                nodeConn.get(currNode).remove((Integer)min);
                nodeLen[currNode]--;
                if(nodeLen[currNode]<nodeLen[newMin])
                    newMin=currNode;
            }
            min = newMin;
            count++;
        }
        if(count!=n){
            path[count]=min+1;
            count++;
        }
        System.out.println(count);
        for (int i=0; i<count; i++){
            System.out.print(path[i] + " ");
        }
    }
}









In   C  :





#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int max=0,max1=0,index,count;

void DFS(int* V,int i,int n,int* parent,int* g[],int q)
{
	
	//printf(" %s ",node1[i].ch);
	V[i] = 1;
    count++;
	///node* temp;
	//temp = node1[i].next;
	int j;
	for(int j=0;j<n;j++)
     {
     if(g[i][j]==1&&V[j]==-1){
		  
			parent[j] = i;
		DFS(V,j,n,parent,g,q+1);
    }

	}
    
    if(q>max)
    {
        max = q;
        index = i;
    }

}

// function for traversal of every non visited nodes

void con_COMP(int size,int* g[])
{
	int visited[size],parent[size];
	int i;
	for(i=0;i<size;i++)
	{
		visited[i] = -1;
		parent[i] = -1;
	}
    int index1;
	for(i = 0;i<size;i++)
	{
		if(visited[i] == -1)
		{
			count = 0;
			//printf("%d.",count);
			DFS(visited,i,size,parent,g,1);
            if(count>max1)
            {
                max1 = count;
                index1 = i;
            }
			//	printf("\n");
		}
	}
    printf("%d\n",max);
   for(int j = index;j!=index1;j=parent[j]) 
    printf("%d ",j+1);
    printf("%d ",index1+1);
    
}

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
   int** graph = (int**)malloc(sizeof(int*)*(n));
	
	for(int i = 0;i < n;i++)
	{
		graph[i] = (int*)malloc(sizeof(int)*(n));
	}
	
    for(int i=0;i<n;i++)
    {
       for(int j=0;j<n;j++)
           graph[i][j] = 0;
    }
    for(int i=0;i<m;i++)
     {
        int v1,v2;
        scanf("%d %d",&v1,&v2);
        graph[v1-1][v2-1] = 1;
        graph[v2-1][v1-1] = 1;
    }
    con_COMP(n,graph);
  
    return 0;
}







In   Python3  :









n,m=map(int,input().split())
roads=[]
dic={}
for i in range(m):
    [x,y]=list(map(int,input().split()))
    roads.append([x,y])
    if not x in dic:dic[x]={y}
    if x in dic:dic[x].add(y)
    if not y in dic:dic[y]={x}
    if y in dic:dic[y].add(x)
count=[0]*(n+1)
for x in dic:
    count[x]=len(dic[x])
_,start=min([[count[z],z] for z in dic],key=lambda a:a[0])
path=[start]
x=start
for i in range(1,n):
    if len(dic[x])==0:break
    _,y=min([[count[z],z] for z in dic[x]],key=lambda a:a[0])
    if x in dic[y]: dic[y].remove(x)
    count[y]-=1
    path.append(y)
    x=y
        
print(len(path))
print(*path, sep=" ")