연결 요소의 개수

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
3 초	512 MB	86464	39394	25976	42.560%

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)

둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v)

같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

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

예제 출력 1

2

예제 입력 2

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

예제 출력 2

1

예제 입력 A

3 2
1 2
3 2

예제 출력 A

1

예제 입력 B

10 3
3 4
4 6
9 6

예제 출력 B

7

예제 입력 C

1000 0

예제 출력 C

1000

예제 입력 D

1 0

예제 출력 D

1

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: djm03178, seoo2001, YunGoon
• 잘못된 조건을 찾은 사람: songjuh

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

자료구조는 2차원 배열을 사용하였다.

arr[N][0] 은 방문 처리 용도

arr[A][B] 가 true면 A – B (연결)을 나타낸다.

이 문제는 시간 제한과 메모리 제한을 보면 BFS / DFS 등 어느 것을 사용해도 상관없는 문제

통과된 코드

#include <iostream>

using namespace std;

int N, M, cnt = 0;

pair<int, int> tempPair;

bool arr[1001][1001];

void CheckNode(int A) // DFS
{
	arr[A][0] = false; // 방문처리
	for (int i = 1; i <= N; i++) {
		if (A == i) continue;

		// 양방향 탐색
		if ((arr[i][0] == true && arr[i][A] == true) || (arr[i][0] == true && arr[A][i] == true)) 
			CheckNode(i);
	}
}


int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	// 자기 자신은 항상 자기 자신의 연결 요소에 속한다.
	for (int i = 1; i <= N; i++) arr[i][0] = true;


	for (int i = 0; i < M; i++) {
		cin >> tempPair.first >> tempPair.second;
		arr[tempPair.first][tempPair.second] = true;
		arr[tempPair.first][0] = true;
		arr[tempPair.second][0] = true;
	}

	for (int i = 1; i <= N; i++) {
		if (arr[i][0] == false) continue; // 방문처리가 되어있다면 넘어간다.
		else 
		{
			CheckNode(i);
			cnt++; // 연결요소 카운트 + 1
		}
	}

	cout << cnt;

	return 0;
}

자기 자신만 있는 경우를 연결 요소로 카운트하지 않아서 방황했다.