C++ [Algorithm] - 백준 11724 연결 요소의 개수

문제

---

입출력

---

문제 요약

무방향 그래프에서 연결된 요소들의 개수를 찾는 것이다.

무방향 그래프에서는 2차원 벡터를 사용해야 한다.

 

2차원 벡터

2차원 벡터라는 것에대해 이해가 잘 안갔는데 자바의 List형태에 배열이랑 구조가 비슷하다.

예제 입력 1을 2차원 백터로 표현하자면

이런 식으로 표현이 될 것이다.

이제 1부터 시작하여 1의 인접 리스트인 2,5를 dfs 진행하면 된다.

---

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int> V[1000];
bool visited[1000];
int cnt = 0;
int N, M;
int a, b;

void init() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

void dfs(int node) {
	visited[node] = true;

	for (int i = 0; i < V[node].size(); i++) {
		int k = V[node][i];
		if (!visited[k]) {
			dfs(k);
		}
	}
}

int main() {
	init();

	cin >> N >> M;

	memset(visited, false, sizeof(visited));

	for (int i = 1; i <= M; i++) {
		cin >> a >> b;
		V[a].push_back(b);
		V[b].push_back(a);
	}

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			dfs(i);
			cnt++;
		}
	}

	cout << cnt;
}