youngyangyang04/leetcode-master-comment

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

Opened this issue · 2 comments

DEZREMNACUI commented

采用领接表的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();
  • 👍1
abinggo commented

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);

}
  • 👍1