Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package graph;
- import java.io.*;
- import java.util.StringTokenizer;
- import java.util.Vector;
- public class Euler_Path implements Runnable {
- class Edge {
- int v1;
- int v2;
- boolean was;
- Edge(int v1, int v2) {
- this.v1 = v1;
- this.v2 = v2;
- was = false;
- }
- }
- int n;
- int m;
- Vector<Vector<Edge>> neigh;
- int[] degree;
- int tmp;
- String ans = "";
- void findPath(int v) {
- Vector<Edge> current = neigh.get(v);
- for(int i = 0; i < current.size(); i++) {
- Edge e = current.get(i);
- if(!e.was) {
- e.was = true;
- tmp = (e.v1 == v) ? e.v2 : e.v1;
- findPath(tmp);
- }
- }
- ans += " " + Integer.toString(v);
- }
- public void run() {
- try {
- BufferedReader in = new BufferedReader(new FileReader("input.txt"));
- PrintWriter out = new PrintWriter("output.txt");
- StringTokenizer st = new StringTokenizer(in.readLine());
- n = Integer.parseInt(st.nextToken());
- neigh = new Vector<Vector<Edge>>(n + 1);
- for(int i = 0; i <= n; i++) {
- neigh.add(new Vector<Edge>());
- }
- degree = new int[n + 1];
- int[][] w = new int[n + 1][n + 1];
- int t;
- Edge e;
- for(int i = 1; i <= n; i++) {
- st = new StringTokenizer(in.readLine());
- int count = Integer.parseInt(st.nextToken());
- for(int j = 0; j < count; j++) {
- t = Integer.parseInt(st.nextToken());
- w[i][t]++;
- }
- }
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) {
- if(w[i][j] > 0) {
- w[i][j]--;
- w[j][i]--;
- e = new Edge(i, j);
- neigh.get(i).add(e);
- neigh.get(j).add(e);
- degree[i]++;
- degree[j]++;
- }
- }
- }
- boolean hasCycle = true;
- boolean hasPath = true;
- int amount = 0;
- for(int i = 1; i <= n; i++) {
- if((degree[i] & 1) != 0) {
- amount++;
- hasCycle = false;
- }
- }
- if(!hasCycle) {
- if (amount != 2) hasPath = false;
- }
- if(hasCycle) {
- findPath(1);
- int len = ans.length() / 2 - 1;
- out.println(len);
- out.print(ans.substring(1));
- } else if(hasPath) {
- int min = 0;
- for(int i = 1; i <= n; i++) {
- if((degree[i] & 1) != 0) {
- min = i;
- break;
- }
- }
- findPath(min);
- int len = ans.length() / 2 - 1;
- out.println(len);
- out.print(ans.substring(1));
- } else out.print("-1");
- in.close();
- out.close();
- } catch(Exception e) {
- e.printStackTrace();
- }
- }
- public static void main(String[] args) {
- new Thread(new Euler_Path()).start();
- }
- }
Add Comment
Please, Sign In to add comment