[11724번] 연결요소

- DFS

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

const int MAX = 1010;
vector<int> myGraph[MAX];
bool visited[MAX];

void dfs(int x)
{
	visited[x] = true;
	
	for(int i = 0; i < myGraph[x].size(); i++)
	{
		int y = myGraph[x][i];
		if(!visited[y])
		{
			dfs(y);
		}
	}
}

int main()
{
	int n,m;
	int cnt = 0;
	scanf("%d %d", &n, &m);
	
	for(int i = 0; i < m; i++)
	{
		int u,v;
		scanf("%d %d", &u, &v);
		myGraph[u].push_back(v);
		myGraph[v].push_back(u);
	}

	//시작점 1~n까지
	for(int i = 1; i <= n; i++)
	{
		if(!visited[i])
		{
			cnt++;
			dfs(i);
		}
	}

	printf("%d", cnt);

	return 0;
}

- BFS

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

const int MAX = 1010;
vector<int> myGraph[MAX];
bool check[MAX];

void bfs(int x)
{
	queue<int> Queue;
	Queue.push(x);
	check[x] = true;
	
	while(!Queue.empty())
	{
		int current = Queue.front();
		Queue.pop();

		for(int i = 0; i < myGraph[current].size(); i++)
		{
			int next = myGraph[current][i];
			if(!check[next])
			{
				check[next] = true;
				Queue.push(next);
			}
		}
	}
	
}

int main()
{
	int n,m;
	int cnt = 0;
	scanf("%d %d", &n, &m);

	for(int i = 0; i < m; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);
		myGraph[u].push_back(v);
		myGraph[v].push_back(u);
	}

	for(int i = 1; i <= n; i++)
	{
		if(!check[i])
		{
			cnt++;
			bfs(i);
		}
	}
	
	printf("%d", cnt);

	return 0;
}