✏️

연결된 정점들

Question

방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.

Test Case 1

input

const result = connectedVertices([
	[0, 1],
	[2, 3],
	[4, 5],
]);
Shell
복사

output

Shell
복사

Solve

BFS

function connectedVertices(edges) {
  const maxVertex = edges.reduce((acc, e) => Math.max(acc, ...e), 0);

  const adjList = {};
  for (let i = 0; i <= maxVertex; i++) {
    adjList[i] = [];
  }
  
  for (let edge of edges) {
    adjList[edge[0]].push(edge[1]);
    adjList[edge[1]].push(edge[0]);
  }

  const visited = new Array(maxVertex).fill(false);
  let count = 0;

  for (let vertex = 0; vertex <= maxVertex; vertex++) {
    if (!visited[vertex]) {
      bfs(adjList, vertex, visited);
      count++;
    }
  }
  return count;
}

function bfs(adjList, vertex, visited) {
  const queue = [vertex];
  visited[vertex] = true;

  while (queue.length > 0) {
    let now = queue.shift();
    for (let i = 0; i < adjList[now].length; i++) {
      if (!visited[adjList[now][i]]) {
        queue.push(adjList[now][i]);
        visited[adjList[now][i]] = true;
      }
    }
  }
}
JavaScript
복사

실행시간 : ms