[BOJ] 11724 : 연결 요소의 개수

Question

---

Solution

• 그래프와 방문처리를 할 graph와 visited를 선언한다.
• 입력으로 주어지는 양끝점 u, v에 대해 서로 이어준다.
• DFS를 실행하고 연결요소의 수 (count)를 구한다.
• count는 정점의 수 n만큼 for문으로 돌리고 맨처음 DFS실행될때만 count를 증가시켜주면 된다.

---

Cord

#include <iostream>
#include <vector>

#define SIZE 1001

using namespace std;

vector<int> graph[SIZE];
bool visited[SIZE];

void dfs(int _x)
{
	if (visited[_x]) { return; }

	visited[_x] = true;
	for (int i = 0; i < graph[_x].size(); i++)
	{
		int n = graph[_x][i];
		dfs(n);
	}
}

int main()
{
	// 정점의수, 간선의 수
	int n, m;
	cin >> n >> m;

	// 간선 연결
	int u, v;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// DFS 실행
	int count = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!visited[i])
		{
			dfs(i);
			count++;
		}
	}

	// 결과 출력
	cout << count;

	return 0;
}

---

Result