Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.*;
- class Vertex {
- boolean mark;
- int x;
- ArrayList<Integer> dists;
- int[][] dist;
- public Vertex(int x) {
- this.x = x;
- dists = new ArrayList<>();
- }
- public static void BFS(Vertex g[], int v1, int[][] dist, int k) {
- int c = 0;
- for (Vertex v : g)
- v.mark = false;
- ArrayDeque<Integer> queue = new ArrayDeque();
- for (Vertex w : g) {
- if (!w.mark) {
- g[v1].mark = true;
- queue.add(v1);
- dist[k][v1] = 0;
- while (!queue.isEmpty()) {
- int v = queue.pop();
- for (int i = 0; i < g[v].dists.size(); i++) {
- int u = g[v].dists.get(i);
- if (!g[u].mark) {
- g[u].mark = true;
- queue.add(u);
- dist[k][u] = dist[k][v] + 1;
- }
- }
- }
- }
- }
- }
- }
- public class EqDist {
- public static void main(String[] args) {
- int N, M, K, v, u, v1;
- //ArrayDeque<Vertex> queue;
- //queue = new ArrayDeque<Vertex>();
- ArrayList<Integer> list = new ArrayList();
- Scanner in = new Scanner(System.in);
- N = in.nextInt();
- M = in.nextInt();
- Vertex[] g = new Vertex[N];
- for (int i = 0; i < N; i++)
- g[i] = new Vertex(i);
- for (int i = 0; i < M; i++) {
- v = in.nextInt();
- u = in.nextInt();
- g[u].dists.add(v);
- g[v].dists.add(u);
- }
- K = in.nextInt();
- int[][] dist = new int[K][N];
- for (int i = 0; i < K; i++) {
- Arrays.sort(dist[i]);
- for (int j = 0; j < N; j++)
- dist[i][j] = -1;
- v1 = in.nextInt();
- Vertex.BFS(g,v1, dist, i);
- }
- for (int i = 0; i < N; i++) {
- int res = 1;
- for (int j = 1; j < K; j++) {
- if ((dist[j][i] == -1) || (dist[j-1][i] != dist[j][i]))
- res = 0;
- }
- if (res == 1)
- list.add(i);
- }
- if (list.size() == 0)
- System.out.println("-");
- else
- for(int i = 0; i < list.size(); i++)
- System.out.print(list.get(i) + " ");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement