Advertisement
Guest User

Untitled

a guest
Mar 18th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.65 KB | None | 0 0
  1. import java.util.ArrayDeque;
  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.Scanner;
  5.  
  6. class Vert {
  7. int x;
  8. boolean mark;
  9. ArrayList<Integer> dists;
  10.  
  11. public Vert(int x) {
  12. this.x = x;
  13. dists = new ArrayList<>();
  14. }
  15.  
  16. public static void BFS(Vert g[], int[][] dist, int v1, int k){
  17. for (Vert v : g)
  18. v.mark = false;
  19. ArrayDeque<Integer> queue = new ArrayDeque();
  20. for (Vert w : g) {
  21. if (!w.mark){
  22. g[v1].mark = true;
  23. queue.add(v1);
  24. dist[k][v1] = 0;
  25. while (!queue.isEmpty()) {
  26. int v = queue.pop();
  27. for (int i = 0; i < g[v].dists.size(); i++) {
  28. int u = g[v].dists.get(i);
  29. if (!g[u].mark) {
  30. g[u].mark = true;
  31. queue.add(u);
  32. dist[k][u] = dist[k][v] + 1;
  33. }
  34. }
  35. }
  36. }
  37. }
  38. }
  39. }
  40.  
  41. public class EqDist {
  42. public static void main(String[] args) {
  43. int N, M, u, v, K, v1;
  44.  
  45. ArrayList<Integer> list = new ArrayList();
  46. Scanner in = new Scanner(System.in);
  47. N = in.nextInt();
  48. M = in.nextInt();
  49.  
  50. Vert[] g = new Vert[N];
  51. for (int i = 0; i < N; i++) {
  52. g[i] = new Vert(i);
  53. }
  54. for (int i = 0; i < M; i++) {
  55. v = in.nextInt();
  56. u = in.nextInt();
  57. g[v].dists.add(u);
  58. g[u].dists.add(v);
  59. }
  60.  
  61. K = in.nextInt();
  62. int[][] dist = new int[K][N];
  63. for (int i = 0; i < K; i++) {
  64. Arrays.sort(dist[i]);
  65. v1 = in.nextInt();
  66. for (int j = 0; j < N; j++) {
  67. dist[i][j] = -1;
  68. }
  69. Vert.BFS(g, dist, v1, i);
  70. }
  71. for (int i = 0; i < N; i++) {
  72. int res = 1;
  73. for (int j = 1; j < K; j++) {
  74. if ((dist[j][i] == -1) || (dist[j-1][i] != dist[j][i]))
  75. res = 0;
  76. }
  77.  
  78. if (res == 1)
  79. list.add(i);
  80. }
  81. /*for (int i = 0; i < K; i++) {
  82. for (int j = 0; j < N; j++) {
  83. System.out.print(dist[i][j] + " ");
  84. }
  85. System.out.println();
  86. }*/
  87.  
  88. if (list.size() == 0)
  89. System.out.println("-");
  90. else {
  91. for (int i = 0; i < list.size(); i++) {
  92. System.out.print(list.get(i) + " ");
  93. }
  94. }
  95. }
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement