BOJ. Let's go on a trip (1976)

Problem link

Treat the cities as vertices and the roads as undirected edges. An itinerary is possible exactly when every city listed in it belongs to the same connected component: then a path exists between each consecutive pair of planned cities, and those paths can be concatenated. A one-city itinerary is therefore always possible.

Use a disjoint-set union (DSU) structure. Initially each city is its own set. For every 1 in the adjacency matrix, union the corresponding cities; processing both directions of the undirected matrix is harmless because unioning a pair already in one set does nothing. Then read the itinerary and compare every city’s representative with the first one’s representative. Path compression shortens future finds, and union by size keeps the trees shallow.

Reading the N × N matrix takes O(N^2) time. DSU operations take amortized O(α(N)) each, so the full time complexity is O(N^2 α(N) + M α(N)); space complexity is O(N). The scanner consumes whitespace rather than splitting individual lines, so arbitrary spaces and line breaks are handled.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    FastScanner input = new FastScanner();
    int cityCount = input.nextInt();
    int planLength = input.nextInt();
    DisjointSet dsu = new DisjointSet(cityCount);

    for (int from = 0; from < cityCount; from++) {
      for (int to = 0; to < cityCount; to++) {
        if (input.nextInt() == 1) {
          dsu.union(from, to);
        }
      }
    }

    int firstCity = input.nextInt() - 1;
    int representative = dsu.find(firstCity);
    for (int i = 1; i < planLength; i++) {
      int city = input.nextInt() - 1;
      if (dsu.find(city) != representative) {
        System.out.println("NO");
        return;
      }
    }

    System.out.println("YES");
  }

  private static final class DisjointSet {
    private final int[] parent;
    private final int[] size;

    DisjointSet(int n) {
      parent = new int[n];
      size = new int[n];
      for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
      }
    }

    int find(int city) {
      if (parent[city] != city) {
        parent[city] = find(parent[city]);
      }
      return parent[city];
    }

    void union(int a, int b) {
      int rootA = find(a);
      int rootB = find(b);
      if (rootA == rootB) return;
      if (size[rootA] < size[rootB]) {
        int temp = rootA;
        rootA = rootB;
        rootB = temp;
      }
      parent[rootB] = rootA;
      size[rootA] += size[rootB];
    }
  }

  private static final class FastScanner {
    private final BufferedInputStream input = new BufferedInputStream(System.in);
    private final byte[] buffer = new byte[1 << 16];
    private int length;
    private int position;

    private int read() throws IOException {
      if (position == length) {
        length = input.read(buffer);
        position = 0;
        if (length == -1) return -1;
      }
      return buffer[position++];
    }

    int nextInt() throws IOException {
      int c;
      do {
        c = read();
      } while (c <= ' ' && c != -1);

      int value = 0;
      while (c > ' ') {
        value = value * 10 + c - '0';
        c = read();
      }
      return value;
    }
  }
}