[실2] 11724 - 연결 요소의 개수

Dfs로 주변 정점이 있는지 파악하고 있을 시 방문 여부 표시 없을 시 새로운 그래프로 간주 후 1개 증가

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0);
#define y first
#define x second

using IntPair = pair<int, int>;

IntPair dir[]
{
	{1, 0},	  // 상
	{-1, 0},  // 하
	{0, -1},  // 좌
	{ 0, 1 },  // 우
};

vector<vector<int>> graph;
vector<bool> vis;
int n, m;

void Dfs(int idx)
{
	vis[idx] = true;
	
	for (int i = 0; i < graph[idx].size(); i++)
	{
		auto nxt = graph[idx][i];

		if (!vis[nxt])
			Dfs(nxt);
	}
}

int main()
{
	FAST_IO();

	int res = 0;
	cin >> n >> m;
	graph = vector<vector<int>>(n + 1);
	vis.resize(n + 1);

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
		{
			Dfs(i);
			res++;
		}
	}
	cout << res;
	return 0;
}