11724번: 연결 요소의 개수

Memo

• 인접 리스트 형태로 값을 저장합니다.
• 각 정점을 모두 방문하며, 처음 방문한 경우 visited체크를 해준 후 dfs를 통해 인접한 노드를 탐색하고 visited체크를 해줍니다.

Code

제출 날짜

2021/03/30

메모리

6384 KB

시간

92 ms

#include <iostream>
#include <vector>

size_t N, M;
std::vector<std::vector<int> >graph;
bool visited[1001];
int ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	int a, b;

	input_faster();
	std::cin >> N >> M;
	graph.resize(N + 1);
	for (size_t i = 0 ; i < M ; i++)
	{
		std::cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
}

void dfs(int i)
{
	for (size_t j = 0 ; j < graph[i].size(); j++)
	{
		if (visited[graph[i][j]])
			continue;
		visited[graph[i][j]] = 1;
		dfs(graph[i][j]);
	}
}

void solve()
{
	for (size_t i = 1 ; i <= N ; i++)
	{
		if (visited[i])
			continue;
		ans++;
		visited[i] = 1;
		dfs(i);
	}
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}