Advertisement
Guest User

Untitled

a guest
Mar 21st, 2018
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.12 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. class Vertex {
  4.     boolean mark;
  5.  
  6.     ArrayList<Integer> data_about_vertexes;
  7.     public Vertex() {
  8.         data_about_vertexes = new ArrayList<>();
  9.     }
  10. }
  11.  
  12. public class EqDist {
  13.  
  14.     private void BFS(int k, int[][] distances_between_u_v, int v_help, Vertex[] g){ //лекции стр 51
  15.         for (int q=0; q<g.length; q++)
  16.             g[q].mark = false;
  17.         ArrayDeque<Integer> queue = new ArrayDeque();
  18.         for (int w=0; w<g.length; w++) {
  19.             if (!g[w].mark) {
  20.                 g[v_help].mark = true;
  21.                 queue.add(v_help);
  22.                 distances_between_u_v[k][v_help] = 0;
  23.                 while (!queue.isEmpty()) {
  24.                     int q = queue.pop();
  25.                     for (int i = 0; i < g[q].data_about_vertexes.size(); i++) {
  26.                         int y = g[q].data_about_vertexes.get(i);
  27.                         if (!g[y].mark) {
  28.                             g[y].mark = true;
  29.                             queue.add(y);
  30.                             distances_between_u_v[k][y] = distances_between_u_v[k][q] + 1;
  31.                         }
  32.                     }
  33.                 }
  34.             }
  35.         }
  36.     }
  37.  
  38.     public static void main(String[] args) {
  39.  
  40.         int N, M, K, v, u, v_help;
  41.  
  42.         //ArrayList<Integer> list = new ArrayList();
  43.         int[] list = new int[100000];
  44.  
  45.         Scanner in = new Scanner(System.in);
  46.         N = in.nextInt();
  47.         M = in.nextInt();
  48.  
  49.         Vertex[] g = new Vertex[N];
  50.         for (int i = 0; i < N; i++)
  51.             g[i] = new Vertex();
  52.  
  53.         for (int i = 0; i < M; i++) {
  54.             v = in.nextInt();
  55.             u = in.nextInt();
  56.             g[u].data_about_vertexes.add(v);
  57.             g[v].data_about_vertexes.add(u);
  58.         }
  59.  
  60.         EqDist eq = new EqDist();
  61.         K = in.nextInt();
  62.         int[][] distances_between_u_v = new int[K][N];
  63.         int ind = 0;
  64.  
  65.         for (int i = 0; i < K; i++) {
  66.             for (int j = 0; j < N; j++)
  67.                 distances_between_u_v[i][j] = 666;
  68.             v_help = in.nextInt();
  69.             eq.BFS(i, distances_between_u_v, v_help, g);
  70.         }
  71.  
  72.  
  73.         for (int i = 0; i < N; i++) {
  74.             //int res = 1;
  75.             boolean res = true;
  76.             for (int j = 1; j < K; j++) {
  77.                 if ((distances_between_u_v[j][i] == 666) || (distances_between_u_v[j-1][i] != distances_between_u_v[j][i]))
  78.                     res = false;
  79.             }
  80.  
  81.             if (res) {
  82.                 list[ind] = i;
  83.                 //System.out.println("list["+ind+"] ="+list[ind]);
  84.                 ind++;
  85.                 //System.out.println("i= "+i);
  86.             }
  87.             //System.out.println("i= "+i);
  88.         }
  89.  
  90.         //Arrays.sort(list); сортировка не нужна в блоке if выше всегда будет
  91.         //System.out.println("ind ="+ind);       расстанавливаться по возрастанию
  92.         if (ind == 0)
  93.             System.out.println("-");
  94.         else
  95.             for(int i = 0; i < ind; i++)
  96.                 System.out.print(list[i] + " ");
  97.     }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement