Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayDeque;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Scanner;
- class Vert {
- int x;
- boolean mark;
- ArrayList<Integer> dists;
- public Vert(int x) {
- this.x = x;
- dists = new ArrayList<>();
- }
- public static void BFS(Vert g[], int[][] dist, int v1, int k){
- for (Vert v : g)
- v.mark = false;
- ArrayDeque<Integer> queue = new ArrayDeque();
- for (Vert 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, u, v, K, v1;
- ArrayList<Integer> list = new ArrayList();
- Scanner in = new Scanner(System.in);
- N = in.nextInt();
- M = in.nextInt();
- Vert[] g = new Vert[N];
- for (int i = 0; i < N; i++) {
- g[i] = new Vert(i);
- }
- for (int i = 0; i < M; i++) {
- v = in.nextInt();
- u = in.nextInt();
- g[v].dists.add(u);
- g[u].dists.add(v);
- }
- K = in.nextInt();
- int[][] dist = new int[K][N];
- for (int i = 0; i < K; i++) {
- Arrays.sort(dist[i]);
- v1 = in.nextInt();
- for (int j = 0; j < N; j++) {
- dist[i][j] = -1;
- }
- Vert.BFS(g, dist, v1, 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);
- }
- /*for (int i = 0; i < K; i++) {
- for (int j = 0; j < N; j++) {
- System.out.print(dist[i][j] + " ");
- }
- System.out.println();
- }*/
- 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