🖊️ 문제

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

---

🖊️ 풀이

처음 보고 이게 뭐지..!? 했다.
전에 그래프 공부할 때 지나간 적이 있는 것 같은데,. 막상 보니 바로 생각이 안났다.

연결요소란 그래프 내에서 나누어진 각각의 그래프를 의미한다.

노드에서 연결된 노드들을 모두 방문하고, 방문이 끝나면 해당 그래프가 하나의 연결노드이다.

이걸 이용해보면, DFS를 통해 이 문제를 쉽게 풀 수 있다.

DFS를 통해 각 노드를 방문하고, 방문이 끝나면 result를 1 더한다. (하나의 연결요소)
아직 방문하지 않은 노드들에 대해 위 과정을 수행하면 끝.

문제 자체는 매우 이지하다

벗..

자꾸 그래프 문제 풀 때마다 visited때문에 삐끗.. 시간 걸리는거 해결하고시프다.

#include <iostream>
#include <vector>
using namespace std;

int N, M;
int result;
vector<vector<int>> vec;
bool visited[1001] = { false, };

void DFS(int n)
{
	visited[n] = true;
	for (int i = 0; i < vec[n].size(); i++) {
		if (visited[vec[n][i]]) continue;
		DFS(vec[n][i]);
	}
}

int main()
{
	cin >> N >> M;
	result = 0;

	for (int i = 0 ; i <= N ; i++)	
		vec.emplace_back(vector<int>());

	int u, v;
	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			DFS(i);
			result++;
		}
	}
	cout << result << endl;
}

---

연결요소 출처