Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.29 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class EqDist {
  4.     private final static int INF = 10000000;
  5.     private static class Graph {
  6.         private int V;
  7.         private ArrayList<ArrayList<Integer>> gr;
  8.         private ArrayList<Integer> dist;
  9.         Graph(int v) {
  10.             V = v;
  11.             gr = new ArrayList<>();
  12.             for (int i = 0; i < v; i++)
  13.                 gr.add(new ArrayList<>());
  14.         }
  15.  
  16.         void addEdge(int u, int v) {
  17.             gr.get(u).add(v);
  18.             if (u != v)
  19.                 gr.get(v).add(u);
  20.         }
  21.  
  22.         void find(int s) {
  23.             char[] visited = new char[V];
  24.             dist = new ArrayList<>(V);
  25.             for (int i = 0; i < V; i++)
  26.                 dist.add(INF);
  27.             dist.set(s, 0);
  28.             while(true){
  29.                 int v = -1;
  30.                 for (int nv = 0; nv < V; nv++)
  31.                     if (visited[nv] == 0 && dist.get(nv) < INF && (v == -1 || dist.get(v) > dist.get(nv)))
  32.                         v = nv;
  33.                 if (v == -1) break;
  34.                 visited[v] = 1;
  35.                 for (int i : gr.get(v))
  36.                     if (visited[i] == 0)
  37.                         dist.set(i, Math.min(dist.get(i), dist.get(v) + 1));
  38.             }
  39.         }
  40.  
  41.         ArrayList<Integer> getDist(){
  42.             return dist;
  43.         }
  44.  
  45.     }
  46.     public static void main(String[] args) {
  47.         Scanner in = new Scanner(System.in);
  48.         int n, m;
  49.         n = in.nextInt();
  50.         m = in.nextInt();
  51.         Graph g = new Graph(n);
  52.         for (int i = 0; i < m; i++) {
  53.             int u = in.nextInt();
  54.             int v = in.nextInt();
  55.             g.addEdge(u, v);
  56.         }
  57.         int k = in.nextInt();
  58.         int v = in.nextInt();
  59.         g.find(v);
  60.         ArrayList<Integer> tmp = g.getDist();
  61.         for (int i = 1; i < k; i++) {
  62.             v = in.nextInt();
  63.             g.find(v);
  64.             for (int j = 0; j < n; j++)
  65.                 if (!tmp.get(j).equals(g.getDist().get(j)))
  66.                     tmp.set(j, -1);
  67.         }
  68.         k = 0;
  69.         StringBuilder res = new StringBuilder();
  70.         for (int i = 0; i < n; i++)
  71.             if (tmp.get(i) != -1 && tmp.get(i) != INF) {
  72.                 res.append(i).append(" ");
  73.                 k++;
  74.             }
  75.         if (k == 0) System.out.println("-");
  76.         else System.out.println(res);
  77.     }
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement