[boj][c++] 11724 연결요소의개수

11724 연결 요소의 개수

처음으로 dfs문제 풀이 안 보고 완전히 내 힘으로 풀었다! 뿌듯하다. 오늘은 꼭 스스로 풀어봐야지 하는 마음가짐으로 손 댄 문제였는데 운이 좋았는지 스터디 준비하면서 풀었던 음료수 얼려 먹기라는 문제와 비슷했다. 로직은 그 문제에서 대부분의 영감을 얻었다.

• n개의 노드를 반복하며 방문한 노드와 연결된 모든 노드를 방문처리한다.
• 반복이 끝나면 몇개의 연결파트가 있는지 알 수 있다.

정말 어렵게 느껴지는 부분도 역시 연습하다보면 풀리는구나 싶다. 그런데 조금 변형되면 다시 손대기 어려워질 것 같다. 이런식으로 며칠 막히는 파트는 꾸준히 연습문제를 풀어야겠다.

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

vector<int> node[1001];
int visit[1001];
int n, m;

bool dfs(int num)
{
	if (visit[num] == 0)
	{
		visit[num] = 1;
		for (int i = 0; i < node[num].size(); i++)
			dfs(node[num][i]);
		return true;
	}
	return false;
}

int main()
{
	int from, to, cnt;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> from >> to;
		node[from].push_back(to);
		node[to].push_back(from);
	}
	cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		if (dfs(i))
			cnt++;
	}
	cout << cnt << "\n";
	return 0;
}