29 lines
815 B
TypeScript
29 lines
815 B
TypeScript
export {};
|
|
|
|
function dfs(now: number, link: number[][], visited: boolean[]): boolean[]{
|
|
if(!visited[now]) visited[now] = true;
|
|
for(let v of link[now]){
|
|
if(!visited[v]) dfs(v, link, visited);
|
|
}
|
|
return visited;
|
|
}
|
|
|
|
const input: string[] = require("fs").readFileSync(0, "utf8").toString().trim().split('\n');
|
|
const [N, M] = input[0].split(' ').map(Number);
|
|
let visited: boolean[] = new Array(N+1).fill(false);
|
|
let link: number[][] = Array.from({length: N+1}, () => []);
|
|
for(let i=1; i<=M; i++) {
|
|
const [u,v] = input[i].split(' ').map(Number);
|
|
link[u].push(v);
|
|
link[v].push(u);
|
|
}
|
|
|
|
let ConnectedComponentCount = 0
|
|
for(let now = 1 ; now<=N; now++){
|
|
if(!visited[now]){
|
|
ConnectedComponentCount++;
|
|
dfs(now, link, visited);
|
|
}
|
|
}
|
|
console.log(ConnectedComponentCount);
|