백준 11724번 (연결 요소의 개수, C++, DFS) / 추가 반례 [BAEKJOON]
문제
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
plaintext
6 5
1 2
2 5
5 1
3 4
4 6예제 출력 1
plaintext
2예제 입력 2
plaintext
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3예제 출력 2
plaintext
1예제 입력 A
plaintext
3 2
1 2
3 2예제 출력 A
plaintext
1예제 입력 B
plaintext
10 3
3 4
4 6
9 6예제 출력 B
plaintext
7예제 입력 C
plaintext
1000 0예제 출력 C
plaintext
1000예제 입력 D
plaintext
1 0예제 출력 D
plaintext
1
자료구조는 2차원 배열을 사용하였다.
arr[N][0] 은 방문 처리 용도
arr[A][B] 가 true면 A - B (연결)을 나타낸다.
이 문제는 시간 제한과 메모리 제한을 보면 BFS / DFS 등 어느 것을 사용해도 상관없는 문제
출처
통과된 코드
cpp
#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;
}자기 자신만 있는 경우를 연결 요소로 카운트하지 않아서 방황했다.
