문제

풀이

그래프의 모든 경우의 수를 탐색하면 되는 문제기 때문에 DFS로 풀었다.

근데 잘 풀고 나서 모든 반례를 대입해도 값은 나오는데 문제가 틀렸다고 나왔다. 그 원인은 각 노드별로 시작을 인덱스로 놓고 도착점을 값으로 넣기만 했는데 자세히 보니 양방향 노드이기 때문에 끝점을 인덱스로 놓고 시작점을 값으로 넣는 코드도 추가하니 정답이라고 나왔다.

코드

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split("\n");

let answer = 0;
let n = +input[0];
let m = +input[1];

let graph = Array.from({length: n+1}, () => new Array());
let visited = Array.from({length: n+1}, () => 0);

for (let i = 2; i < m + 2; i++) {
    let start = +input[i].split(" ")[0];
    let end = +input[i].split(" ")[1];

    graph[start].push(end);
    graph[end].push(start);
}


function DFS(v) {
    if (graph[v].length === 0) {
        return;
    } else {
        for (let i = 0; i < graph[v].length; i++) {
            if (visited[graph[v][i]] === 0) {
                visited[graph[v][i]] = 1;
                answer++;
                DFS(graph[v][i]);
            }
        }
    }
}

visited[1] = 1;
DFS(1);
console.log(answer);