[Vssue]kamacoder/0105.有向图的完全可达性.md

[youngyangyang04]

https://www.programmercarl.com/kamacoder/0105.%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%AE%8C%E5%85%A8%E5%8F%AF%E8%BE%BE%E6%80%A7.html

[DEZREMNACUI]

采用领接表的ts版本

import { createInterface } from "readline/promises";

const rl = createInterface({
  input: process.stdin,
});

const readline = async () =>
  (await rl[Symbol.asyncIterator]().next()).value as string;

const main = async () => {
  const [N, K] = (await readline()).split(" ").map(Number);
  const linkTable = Array.from({ length: N + 1 }, () => [] as number[]);
  for (let i = 0; i < K; i++) {
    const [source, target] = (await readline()).split(" ").map(Number);
    linkTable[source].push(target);
  }
  const visited = new Set();
  const dfs = (target: number) => {
    visited.add(target);
    linkTable[target].forEach((item) => {
      if (!visited.has(item)) dfs(item);
    });
  };
  dfs(1);
  for (let i = 1; i <= N; i++) {
    if (!visited.has(i)) {
      return -1;
    }
  }
  return 1;
};

const res = await main();
console.log(res);
rl.close();

[abinggo]

java版本 bfs public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[][] edges = new int[n][m]; for (int i = 0; i < m; i++) { int a = scanner.nextInt(); int b = scanner.nextInt(); edges[a-1][b-1] = 1; } boolean[] visited = new boolean[n]; Queue okpath = new LinkedList<>(); okpath.add(0); visited[0] = true; while (!okpath.isEmpty()) { int size = okpath.size(); for (int i = 0; i < size; i++) { int cur = okpath.poll(); for (int j = 0; j < edges[cur].length; j++) { if(edges[cur][j] == 1&&visited[j]==false){ visited[j] = true; okpath.add(j); } } } } for (int i = 0; i < n; i++) { if(visited[i]==false){ System.out.println(-1); return; } } System.out.println(1);

}