[백준][C++] 11724번: 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

정점의 개수와 간선의 양 끝점이 주어졌을 때 연결 요소의 개수를 구하는 문제이다.

 

예제 입력1은 연결된 구역이 2개로 연결 요소의 개수가 2이고

예제 입력2는 모든 정점이 연결되어있어서 연결 요소의 개수가 1이다.

 

간선의 정보를 통해 정점끼리의 '연결성'을 프로그래밍 언어로 어떻게 표현할 것인가가 핵심이다.

이를 위해 정점의 부모 정점을 사용할 것이다.

 

예제 입력1을 통해 살펴보자.

먼저 모든 정점의 부모 정점을 자기 자신으로 설정한다.

1	2	3	4	5	6
1	2	3	4	5	6

 

첫 간선 정보를 통해 정점 1과 2가 연결되었다. 연결된 정점 중 더 작은 정점을 부모 정점으로 갱신하자.

이를 통해 부모 정점을 갱신해주면 다음과 같다.

1	2	3	4	5	6
1	1	3	4	5	6

 

모든 간선에 대해 갱신해보면 다음과 같다.

1	2	3	4	5	6
1	1	3	3	1	3

 

그러면 각 정점의 부모 정점을 통해 연결 요소의 개수가 2개라는 것을 알 수 있다.

 

다음 예제 입력2를 통해 모든 간선에 대해 부모 정점을 갱신해보면 다음과 같은데

1	2	3	4	5	6
1	1	1	1	1	3

 

결과만 보면 연결 요소가 2개가 되는데 사실 3의 부모 정점이 1이므로 6의 부모 정점도 1이 되야 한다.

따라서 모든 간선에 대해 갱신해주고 다시 한 번 모든 정점에 대해 부모 정점을 재귀적으로 갱신해줘야 한다는 것을 알 수 있다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int parent[1001];

int getParent(int x) {
	if(parent[x] == x) return x;
	return parent[x] = getParent(parent[x]);
}

void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if(a<b) parent[b] = a;
	else parent[a] = b;
}

int main(void) {
	int N, M;
	cin >> N >> M;
	
	for(int i=1; i<=N; i++) {
		parent[i] = i;
	}
	
	int u, v;
	for(int i=0; i<M; i++) {
		cin >> u >> v;
		unionParent(u, v);
	}
	
	for(int i=1; i<=N; i++) {
		int x = getParent(i);
		unionParent(i, x);
	}
	
	int cnt=1;
	sort(parent, parent+N);
	int first = parent[1];
	for(int i=1; i<=N; i++) {
		if(first != parent[i]) {
			first = parent[i];
			cnt++;	
		} 
	}
	
	cout << cnt;
}

 

 

맞긴했지만 깔끔하게 맞아 떨어지는 풀이는 아닌 것 같다.

 

그래서 그래프 탐색으로도 풀어봤다.

1부터 N까지 모든 정점에 대해 그래프 탐색을 해주며 방문 처리를 했다. 만약 정점 1과 연결된 정점들은 1에서 시작한 탐색에서 전부 방문 처리가 된다. 만약 연결이 안 되어있다면 방문 처리가 안 된다.

따라서 모든 정점을 돌며 방문 처리가 안 된 정점은 그래프 탐색을 해주고 연결 요소의 개수를 하나 올리는 것으로 풀어봤다.

#include <iostream>
#include <vector>

using namespace std;

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

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

int main(void) {
	int N, M;
	cin >> N >> M;
	
	int u, v;
	for(int i=0; i<M; i++) {
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	
	int cnt=0;
	for(int i=1; i<=N; i++) {
		if(!visited[i]) {
			dfs(i);
			cnt++;	
		}
	}
	
	cout << cnt;
}