Cycle in a Graph

Question

This is a question from Codeforces PC which can be viewed here.

You've got a undirected graph G, consisting of n nodes. We will consider the nodes of the graph indexed by integers from 1 to n. We know that each node of graph G is connected by edges with at least k other nodes of this graph. Your task is to find in the given graph a simple cycle of length of at least k + 1.

A simple cycle of length d (d > 1) in graph G is a sequence of distinct graph nodes v1, v2, ..., vd such, that nodes v1 and vd are connected by an edge of the graph, also for any integer i (1 ≤ i < d) nodes vi and vi + 1 are connected by an edge of the graph. Input

The first line contains three integers n, m, k (3 ≤ n, m ≤ 105; 2 ≤ k ≤ n - 1) — the number of the nodes of the graph, the number of the graph's edges and the lower limit on the degree of the graph node. Next m lines contain pairs of integers. The i-th line contains integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the indexes of the graph nodes that are connected by the i-th edge.

It is guaranteed that the given graph doesn't contain any multiple edges or self-loops. It is guaranteed that each node of the graph is connected by the edges with at least k other nodes of the graph. Output

In the first line print integer r (r ≥ k + 1) — the length of the found cycle. In the next line print r distinct integers v1, v2, ..., vr (1 ≤ vi ≤ n) — the found simple cycle.

It is guaranteed that the answer exists. If there are multiple correct answers, you are allowed to print any of them.

Input:

3 3 2 1 2 2 3 3 1

Output:

3 1 2 3

My Approach:

I used DFS, but got Time Limit Exceeded(TLE). Not getting any idea how to do it fast.

Answer 1

I think DFS using lists of neighbours for each node should meet the time limit if you make sure that the search never backtracks.

The basic idea of DFS is to visit any node which has not yet been visited and recurse.

We stop being able to recurse once we reach a node x, say, for which all of its neighbours have already been visited. It must have at least k neighbours due to the problem statement.

A cycle of length k+1 is formed by returning to the neighbour node which was encounted first.

We can easily determine which node was encounted first by storing the recursion depth at which a node was visited in an array.

EXPLANATION

Suppose we have reached node x with neighbours a,b,c,d all of which have already been visited.

This means that we must have traced out a path that looks something like:

start->...->a->..->b->..->c->..->d->..->x

and so by looping from x to a we have a cycle of at least length k+1. (k because we have k neighbours a,b,c,d and +1 because we also include the node x.)