Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class EqDist {
- private final static int INF = 10000000;
- private static class Graph {
- private int V;
- private ArrayList<ArrayList<Integer>> gr;
- private ArrayList<Integer> dist;
- Graph(int v) {
- V = v;
- gr = new ArrayList<>();
- for (int i = 0; i < v; i++)
- gr.add(new ArrayList<>());
- }
- void addEdge(int u, int v) {
- gr.get(u).add(v);
- if (u != v)
- gr.get(v).add(u);
- }
- void find(int s) {
- char[] visited = new char[V];
- dist = new ArrayList<>(V);
- for (int i = 0; i < V; i++)
- dist.add(INF);
- dist.set(s, 0);
- while(true){
- int v = -1;
- for (int nv = 0; nv < V; nv++)
- if (visited[nv] == 0 && dist.get(nv) < INF && (v == -1 || dist.get(v) > dist.get(nv)))
- v = nv;
- if (v == -1) break;
- visited[v] = 1;
- for (int i : gr.get(v))
- if (visited[i] == 0)
- dist.set(i, Math.min(dist.get(i), dist.get(v) + 1));
- }
- }
- ArrayList<Integer> getDist(){
- return dist;
- }
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int n, m;
- n = in.nextInt();
- m = in.nextInt();
- Graph g = new Graph(n);
- for (int i = 0; i < m; i++) {
- int u = in.nextInt();
- int v = in.nextInt();
- g.addEdge(u, v);
- }
- int k = in.nextInt();
- int v = in.nextInt();
- g.find(v);
- ArrayList<Integer> tmp = g.getDist();
- for (int i = 1; i < k; i++) {
- v = in.nextInt();
- g.find(v);
- for (int j = 0; j < n; j++)
- if (!tmp.get(j).equals(g.getDist().get(j)))
- tmp.set(j, -1);
- }
- k = 0;
- StringBuilder res = new StringBuilder();
- for (int i = 0; i < n; i++)
- if (tmp.get(i) != -1 && tmp.get(i) != INF) {
- res.append(i).append(" ");
- k++;
- }
- if (k == 0) System.out.println("-");
- else System.out.println(res);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement