목록요소 (1)

N

(백준 c++)11724 연결 요소의 개수

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. N개의 노드와 M개의 간선을 그래프로 나타낸 후, DFS를 통해 연결 요소의 개수를 확인한다. 방향이 없기 때문에 graph[u][v] = true, graph[v][u] = true로 하여 한번 방문했던 노드는 방문하지 않도록 처리해야 한다. 또한, visited 벡터도 함께..
백준 알고리즘 2021. 6. 25. 15:35
이전 Prev 1 Next 다음