Cod sursa(job #2022816)

Utilizator gabib97Gabriel Boroghina gabib97 Data 17 septembrie 2017 13:49:07
Problema Ciclu Eulerian Scor 50
Compilator java Status done
Runda Arhiva educationala Marime 2.28 kb
import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static boolean[] o;
    static Vector<Integer>[] G;
    static ArrayList<Integer> r;

    private static void DFS() {
        Stack<Integer> S = new Stack<>();
        S.push(1);

        int x, y;
        while (!S.empty()) {
            x = S.peek();

            if (!G[x].isEmpty()) {
                y = G[x].get(0);
                S.push(y);

                // delete edge
                G[x].remove(0);
                G[y].removeElement(x);
            } else {
                S.pop();
                r.add(x);
            }
        }
    }

    private static void BFS() {
        ArrayDeque<Integer> Q = new ArrayDeque<>();
        int x;
        Q.add(1);

        while (!Q.isEmpty()) {
            x = Q.poll();
            o[x] = true;

            for (int y : G[x])
                if (!o[y]) Q.add(y);
        }
    }

    public static void main(String[] args) throws IOException {
        Scan cin = new Scan("ciclueuler.in");
        PrintWriter cout = new PrintWriter("ciclueuler.out");

        int i;
        n = cin.nextInt();
        m = cin.nextInt();
        o = new boolean[n + 1];
        r = new ArrayList<>(n + 1);
        G = new Vector[n + 1];
        for (i = 1; i <= n; i++) G[i] = new Vector<>();

        int x, y;
        while (m-- != 0) {
            x = cin.nextInt();
            y = cin.nextInt();
            G[x].add(y);
            G[y].add(x);
        }

        BFS();
        for (i = 1; i <= n; i++)
            if (!o[i] || G[i].size() % 2 != 0) break;

        if (i <= n)
            cout.print("-1");
        else {
            DFS();

            for (int e : r) cout.print(e + " ");
        }

        cout.close();
    }

    private static class Scan {
        BufferedReader bufferedReader;
        StringTokenizer st;

        Scan(String file) throws FileNotFoundException {
            bufferedReader = new BufferedReader(new FileReader(file));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreElements())
                st = new StringTokenizer(bufferedReader.readLine());

            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}