[백준]C++ 11742(연결 요소의 개수)

#include <iostream>
#include <vector>

using namespace std;

vector<int> v[1001];
int visited[1001];

void DFS(int a);

int main(void)
{
	int a=0;
	int b=0;
	
	cin>>a>>b;
	
	for(int i=0; i<b; i++)
	{
		int num1=0;
		int num2=0;
		cin>>num1>>num2;
		
		v[num1].push_back(num2);
		v[num2].push_back(num1);
	}
	
	int count=0;
	
	for(int i=1; i<=a; i++)
	{
		if(visited[i]==0)
		{
			visited[i]=1;
			DFS(i);
			count++;
		}
		
	}
	
	cout<<count;
	
	
	return 0;
}

void DFS(int a)
{
	for(int i=0; i<v[a].size(); i++)
	{
		if(visited[v[a][i]]==0)
		{
			visited[v[a][i]]=1;
			DFS(v[a][i]);
		}
	}
}

 

이 문제는 처음에 연결 요소의 개수? 이게 무슨말인지 싶었다.

이거만 이해하면 풀기는 어렵지 않다.

나는 이 문제를 DFS로 풀었다.

처음에 1부터 시작해서 깊게 탐색을 한다. 1과 연결된 부분은 모두 방문처리하고, 방문처리가 된 정점은 다시 방문하지 않는다.

for(int i=1; i<=a; i++)
{
if(visited[i]==0)
{
visited[i]=1;
DFS(i);
count++;
}
}

이 부분에서 이미 방문된 정점이면 방문하지 않는다. 이게 연결 요소의 개수를 찾는 핵심이다.