백준 11724번 : 연결 요소의 개수

문제 접근

---

말 그대로 연결 요소의 개수를 구하는 문제여서, DFS 로 풀었다. 한 연결 요소에 포함되어있는 모든 정점은 그 중 하나의 정점에 대하여 dfs() 를 호출하면 다 방문하게 되니, main 에서 dfs 를 호출하는 횟수가 연결 요소의 개수가 된다.

 

 

문제 코드

---

#include <iostream>
#include <vector>

using namespace std;

// 인접 리스트
vector<vector<int>> adj(1001);
bool visited[1001] = {false,};

void dfs(int n)
{
	// dfs() 호출할 때 해당 정점 방문한 걸로 처리
	visited[n] = true;
	
	for(int i=0; i<adj[n].size(); ++i)
	{
    	// n번 정점에 연결되어있는 정점중 방문하지 않은 정점이 있다면 dfs() 호출
		if(!visited[adj[n][i]])
		{
			dfs(adj[n][i]);
		}
	}
}

int main(void)
{
	int N,M,start,end, ans=0;
	
	cin>>N>>M;
	
	for(int i=0; i<M; ++i)
	{
		cin>>start>>end;
		adj[start].push_back(end);
		adj[end].push_back(start);
	}
	
	for(int i=1; i<=N; ++i)
	{
		if(!visited[i])
		{
			dfs(i);
			++ans;
		}
	}
	
	cout<<ans<<'\n';
}