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

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

11724번: 연결 요소의 개수

모든 정점들을 확인하는데, 방문이 안된 정점을 발견하면 그곳에서 dfs를 진행하고 진행한 부분들이 하나의 연결 요소가 된다.

 

코드

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

int n, m;
vector<vector<int>> adj;
vector<bool> visited;

void dfsSolve(int here)
{
	//방문한것을 체크한다
	visited[here] = true;

	//연결되어있는 정점들중 방문하지 않은 정점들을 dfs로 방문한다
	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];
		if (!visited[there])
			dfsSolve(there);
	}
}

//연결 요소의 개수를 구한다
int Solve()
{
	int ret = 0;

	//모든 정점들을 확인한다
	for (int i = 1; i <= n; i++)
	{
		//방문하지 않은 정점을 발견하면 연결요소를 발견한것이므로
		//이곳에서 dfs를 진행한다
		if (!visited[i])
		{
			//연결 요소 개수 증가
			ret++;

			dfsSolve(i);
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int u, v;

	cin >> n >> m;

	adj = vector<vector<int>>(n + 1);
	visited = vector<bool>(n + 1, false);

	//간선을 입력받아 그래프를 생성한다
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cout << Solve();

	return 0;
}