Connected Component

문제 복기

그래프 상에서 간선 없이 서로 떨어진 두 개의 그래프를 각각 하나의 요소라고 했을 때, 이 그래프는 2개의 요소로 이루어졌다고 할 수 있다.

연결 요소의 갯수는 BFS 또는 DFS로 구할 수 있다. BFS/DFS로 한 노드에서 시작해 그와 연결된 인접 노드들을 다 방문하면 그것은 하나의 연결요소라고 할 수 있으므로, DFS/BFS 한번 돌 때마다 갯수를 1씩 증가시켜주고 모든 노드를 다 방문하고 나서 최종의 갯수가 연결 요소의 갯수라고 할 수 있다.

boolean[] check = new boolean[n+1];
		int ans = 0;
		for(int i=1;i<=n;i++) {
			if(check[i]==false) {
				dfs(a,check,i);
				ans+=1;
			}
		}