Guest User

Untitled

a guest
Jul 18th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.67 KB | None | 0 0
  1. package graph;
  2.  
  3. import java.io.*;
  4.  
  5. import java.util.StringTokenizer;
  6. import java.util.Vector;
  7.  
  8. public class Euler_Path implements Runnable {
  9.  
  10. class Edge {
  11. int v1;
  12. int v2;
  13. boolean was;
  14.  
  15. Edge(int v1, int v2) {
  16. this.v1 = v1;
  17. this.v2 = v2;
  18. was = false;
  19. }
  20. }
  21.  
  22. int n;
  23. int m;
  24.  
  25. Vector<Vector<Edge>> neigh;
  26. int[] degree;
  27.  
  28. int tmp;
  29.  
  30. String ans = "";
  31.  
  32. void findPath(int v) {
  33. Vector<Edge> current = neigh.get(v);
  34.  
  35. for(int i = 0; i < current.size(); i++) {
  36. Edge e = current.get(i);
  37.  
  38. if(!e.was) {
  39.  
  40. e.was = true;
  41. tmp = (e.v1 == v) ? e.v2 : e.v1;
  42.  
  43.  
  44. findPath(tmp);
  45. }
  46. }
  47. ans += " " + Integer.toString(v);
  48. }
  49.  
  50. public void run() {
  51. try {
  52. BufferedReader in = new BufferedReader(new FileReader("input.txt"));
  53. PrintWriter out = new PrintWriter("output.txt");
  54. StringTokenizer st = new StringTokenizer(in.readLine());
  55.  
  56. n = Integer.parseInt(st.nextToken());
  57.  
  58. neigh = new Vector<Vector<Edge>>(n + 1);
  59.  
  60. for(int i = 0; i <= n; i++) {
  61. neigh.add(new Vector<Edge>());
  62. }
  63.  
  64. degree = new int[n + 1];
  65.  
  66. int[][] w = new int[n + 1][n + 1];
  67.  
  68. int t;
  69. Edge e;
  70.  
  71. for(int i = 1; i <= n; i++) {
  72. st = new StringTokenizer(in.readLine());
  73.  
  74. int count = Integer.parseInt(st.nextToken());
  75.  
  76. for(int j = 0; j < count; j++) {
  77. t = Integer.parseInt(st.nextToken());
  78.  
  79. w[i][t]++;
  80. }
  81. }
  82.  
  83. for(int i = 1; i <= n; i++) {
  84. for(int j = 1; j <= n; j++) {
  85. if(w[i][j] > 0) {
  86. w[i][j]--;
  87. w[j][i]--;
  88.  
  89. e = new Edge(i, j);
  90.  
  91. neigh.get(i).add(e);
  92. neigh.get(j).add(e);
  93.  
  94. degree[i]++;
  95. degree[j]++;
  96. }
  97. }
  98. }
  99.  
  100. boolean hasCycle = true;
  101. boolean hasPath = true;
  102.  
  103. int amount = 0;
  104.  
  105. for(int i = 1; i <= n; i++) {
  106. if((degree[i] & 1) != 0) {
  107. amount++;
  108. hasCycle = false;
  109. }
  110. }
  111.  
  112. if(!hasCycle) {
  113. if (amount != 2) hasPath = false;
  114. }
  115.  
  116. if(hasCycle) {
  117. findPath(1);
  118. int len = ans.length() / 2 - 1;
  119.  
  120. out.println(len);
  121. out.print(ans.substring(1));
  122. } else if(hasPath) {
  123. int min = 0;
  124.  
  125. for(int i = 1; i <= n; i++) {
  126. if((degree[i] & 1) != 0) {
  127. min = i;
  128. break;
  129. }
  130. }
  131.  
  132. findPath(min);
  133.  
  134. int len = ans.length() / 2 - 1;
  135.  
  136. out.println(len);
  137. out.print(ans.substring(1));
  138.  
  139. } else out.print("-1");
  140.  
  141. in.close();
  142. out.close();
  143. } catch(Exception e) {
  144. e.printStackTrace();
  145. }
  146. }
  147.  
  148. public static void main(String[] args) {
  149. new Thread(new Euler_Path()).start();
  150. }
  151. }
Add Comment
Please, Sign In to add comment