[백준] 11724번 - 연결 요소의 개수

https://www.acmicpc.net/problem/11724

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. $(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)$ 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. $(1 ≤ u, v ≤ N, u ≠ v)$ 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

---

문제 풀이

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [[] for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)
    arr[a].sort()
    arr[b].sort()

def dfs(v):
    visited[v] = True

    for i in arr[v]:
        if not visited[i]:
            visited[i] = True
            dfs(i)

cnt = 0
for i in range(1, n + 1):
    if not visited[i]:  # 만약 방문하지 않은 부분이라면 cnt += 1하고 dfs에 넣어준다.
        cnt += 1
        dfs(i)

print(cnt)

예제 1번에서 (1, 2, 5), (3, 4, 6) 두 묶음으로 연결되어 있다.
for i in range(1, n+1)문으로 1번부터 방문을 시작한다면 처음에는 visited[1]=False로 되어 있으므로 dfs(1)을 실행하게 된다. 1번과 연결된 정점 2와 5도 마찬가지로 방문되기 때문에 visited[2] = visited[5] = True 가 된다.
그 다음 i = 2가 된다면 이미 노드 2번은 방문상태이므로 dfs에 들어가지 않게 된다. 마찬가지로 i=5도 dfs에 들어가지 않는다.
그러나, 3번 노드는 아직 visited[3]=True 상태이므로 3번부터 다시 dfs가 시작된다.

---

오래 걸렸던 부분

처음에는 if not visited[i] 를 넣지 않아서 계속 cnt가 다르게 출력되었다.

cnt = 0
for i in range(1, n + 1):
    if not visited[i]: 
        cnt += 1
        dfs(i)

---

java로 풀이

• 방향 없는 그래프이므로 양방향 모두 넣어줘야 한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.text.DateFormatSymbols;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

public class Main {

	private static int n, m;
	private static boolean[] visited;
	private static List<Integer>[] graph;

	public static void main(String[] args) throws Exception {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] split = in.readLine().split(" ");
		n = Integer.parseInt(split[0]);
		m = Integer.parseInt(split[1]);

		visited = new boolean[n + 1];
		graph = new ArrayList[n + 1];
		for (int i = 0; i <= n; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int i = 0; i < m; i++) {
			split = in.readLine().split(" ");
			int u = Integer.parseInt(split[0]);
			int v = Integer.parseInt(split[1]);
			graph[u].add(v);
			graph[v].add(u);

		}

		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				find(i);
				cnt++;
			}
		}
		System.out.println(cnt);

	}

	private static void find(int curr) {

		visited[curr] = true;
		for (int v : graph[curr]) {
			if (!visited[v]) {
				visited[v] = true;
				find(v);
			}
		}

	}

}