これは Codeforces PC からの質問で、ここで見ることができます。
n 個のノードで構成される無向グラフ G があります。1 から n までの整数でインデックス付けされたグラフのノードを考えます。グラフ G の各ノードは、このグラフの少なくとも k 個の他のノードとエッジで接続されていることがわかっています。あなたの仕事は、与えられたグラフで少なくとも k + 1 の長さの単純なサイクルを見つけることです。
グラフ G の長さ d (d > 1) の単純なサイクルは、任意の整数に対して、ノード v1 と vd がグラフのエッジによって接続されるような一連の別個のグラフ ノード v1、v2、...、vd です。 i (1 ≤ i < d) ノード vi と vi + 1 は、グラフのエッジによって接続されます。入力
最初の行には、3 つの整数 n、m、k (3 ≤ n、m ≤ 105; 2 ≤ k ≤ n - 1) が含まれます — グラフのノードの数、グラフのエッジの数、およびグラフ ノードの次数。次の m 行には、整数のペアが含まれています。i 番目の行には、整数 ai、bi (1 ≤ ai、bi ≤ n; ai ≠ bi) が含まれます。これは、i 番目のエッジによって接続されたグラフ ノードのインデックスです。
指定されたグラフに複数のエッジや自己ループが含まれていないことが保証されています。グラフの各ノードがエッジによって、グラフの少なくとも k 個の他のノードと接続されていることが保証されます。出力
最初の行に整数 r (r ≥ k + 1) — 見つかったサイクルの長さを出力します。次の行に、r 個の異なる整数 v1、v2、...、vr (1 ≤ vi ≤ n) を出力します — 見つかった単純なサイクル。
答えが存在することが保証されています。正解が複数ある場合は、どれでも印刷できます。
入力：
3 3 2 1 2 2 3 3 1
出力：
3 1 2 3
私のアプローチ:
DFS を使用しましたが、Time Limit Exceeded(TLE) になりました。それを速くする方法がわかりません。