[11724] 연결 요수의 개수

간만에 알고리즘 문제를 풀어본다. 

 

문제요약

- 연결된 요소들의 집합의 개수를 구하라.

- 탐색 알고리즘을 통해 쉽게 해결할 수 있다.(DFS, BFS)

- DFS 방법을 통해 방문한 노드들을 체크해가며 연결되어진 그룹들을 찾는다.

- 시작노드에서 이미 방문한 노드로 체크가 되었다면 무시

- 시작노드에서 방문하지 않은 노드라면 집합의 개수 추가

 

#include <iostream>
#include <vector>
#define MAX		1000+2
using namespace std;
int n, m;
bool visited[MAX];
vector<int> v[MAX];
void Search(int start)
{
	for (int i = 0; i < v[start].size(); i++)
	{
		int end = v[start][i];
		if (!visited[end])
		{
			visited[end] = true;
			Search(end);
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int ret = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			Search(i);
			ret++;
		}
	}

	cout << ret << endl;

	return 0;
}

* 서로 다른 노드들은 하나의 간선을 공유한다.

즉, vector 로 노드들의 정보들을 추가할때 양쪽 모두 추가해주는 것을 잊지말자.

예) (x) - (y)

vector[x].push_back(y);

vector[y].push_back(x);

 

끝.