Advertisement
Guest User

Untitled

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