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

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

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• DFS
• BFS

---

문제 설명

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

---

입력 설명

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

---

출력 설명

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

 

---

예제 입력

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

 

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

---

예제 출력

2

1

---

아이디어

인접행렬로 컴포넌트 연결 상태를 표현하고 DFS를 이용해서 연결된 것들끼리 같은 숫자로 마킹한다.

이후 연결된 컴포넌트의 개수를 출력한다.

---

알고리즘

아무것도 연결되지 않은 상태의 컴포넌트의 개수를 기록하기 위해 1 ~ n 까지 i번 반복하여

인접행렬 벡터 vec[i][i]에 마킹해준다.

이후 간선으로 연결된 정점 a, b를 입력받아 vec[a][b], vec[b][a]에도 마킹해준다.

DFS를 이용하여 연결된 모든 정점을 방문하며 현재까지의 컴포넌트의 개수를 마킹해준다.

main 함수에서 진입하는 DFS가 끝날 때마다 컴포넌트의 개수를 1씩 증가시킨다.

모든 탐색이 종료되면 인접행렬을 모두 방문하며 가장 높은 숫자를 찾아서 출력한다.

---

코드

#include <iostream>
#include <vector>
using namespace std;
int n, m, a, b, num = 1;
void DFS(vector<vector<int>> &vec, int i, int z)
{
    for(int k = 1; k<=n; k++)
    {
        if(vec[i][k] == -1) 
        {
            vec[i][k] = z;
            vec[k][i] = z;
            DFS(vec,k,z);
        }
    }         
}

int main() {
    cin>>n>>m;
    vector<vector<int>> vec(n+1, vector<int>(n+1, 0));
    for(int i = 1;i<=n; i++)
        vec[i][i] = -1;
    for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            vec[a][b] = -1;
            vec[b][a] = -1;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                {
                    if(vec[i][j]==-1)
                    {
                        DFS(vec, i, num);
                        num++;
                    }
                }
        }
    int max = 0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(max < vec[i][j]) max = vec[i][j]; 
    cout<<max;
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/11724

예제의 입력이 모두 맞는데 항상 40%에서 틀린다면, 간선이 0개 일지라도 컴포넌트는 0개가 아니라는 사실을 생각해보자.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!