Есть такой вариант с использованием стека. Начинаете идти с любой вершины. Идете по ребрам, которые еще вообще не использованы, в соседние вершины. Каждую вершину закидываете в стек. Когда не можете найти свободное ребро начинаете скидывать со стека (как бы идти назад) и опять проверяете на наличие полностью пустых вершин (ведь наверняка у какой-то вершины до были несколько пустых ребер. В итоге вы обойдете все ребра и ваш стек станет пустым. Вы обошли весь граф. Поздравления и овации.
Код на java, здесь большой класс InputReader для быстрого чтения:
public class TwiceEdgesTraversal {
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
Solver solver = new Solver();
solver.solve(in, out);
out.close();
}
private static class Solver {
private List<List<Integer>> g;
private boolean[][] were;
private List<Integer> ans;
private void route(Stack<Integer> st) {
if (st.empty())
return;
int v = st.peek();
ans.add(v);
for (int u : g.get(v)) {
if (!were[v][u] && !were[u][v]) {
were[v][u] = true;
st.add(u);
route(st);
return;
}
}
st.pop();
route(st);
}
private void solve(InputReader in, PrintWriter out) {
int n = in.nextInt();
int m = in.nextInt();
g = new ArrayList<>();
for (int i = 0; i <= n; i++)
g.add(new ArrayList<>());
were = new boolean[n + 1][n + 1];
for (int i = 0; i < m; i++) {
int v = in.nextInt();
int u = in.nextInt();
g.get(v).add(u);
g.get(u).add(v);
}
Stack<Integer> st = new Stack<>();
st.add(1);
ans = new ArrayList<>();
route(st);
out.println(ans.size() - 1);
for (int v : ans)
out.println(v);
}
}
private static class InputReader {
private BufferedReader br;
private StringTokenizer st;
public InputReader(InputStream stream) {
br = new BufferedReader(new InputStreamReader(stream));
}
private int nextInt() {
return Integer.parseInt(next());
}
private long nextLong() {
return Long.parseLong(next());
}
private double nextDouble() {
return Double.parseDouble(next());
}
private String nextLine() {
String s = "";
try {
s = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return s;
}
private String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
}
}