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

11724번: 연결 요소의 개수

무방향 그래프 이므로 u와 v를 입력받으면

벡터[u]=v, 벡터[v]=u

를 넣어준다.

 

벡터가 empty될 때까지 방문하지 않은 곳만 DFS로 탐색해주고

한 번이라도 방문한 곳은 visited로 표시해준다.

 

여기서 주의할 점은 간선을 가지지 않는 정점도 하나의 연결 요소로 취급하므로

먼저 벡터가 empty인 애들의 수부터 전부 카운트 해주는 것이 포인트이다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> v[1001];
int visited[1001] = { 0 };
void Dfs(int idx) {
	visited[idx] = 1;
	while (!v[idx].empty()) {
		int temp = v[idx].back();
		v[idx].pop_back();
		if (!visited[temp]) Dfs(temp);
	}
}

int main() {
	int N, M, U, V;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> U >> V;
		v[U].push_back(V);
		v[V].push_back(U);
	}

	int cnt = 0;
	for (int i = 1; i <= N; i++) if (v[i].empty()) cnt++; //간선이 없는 노드도 요소 중 하나이다
	for (int i = 1; i <= N; i++) {
		if (!visited[i] && !v[i].empty()) {
			Dfs(i);
			cnt++;
		}
	}

	cout << cnt;

	return 0;
}