BOJ - 11724. 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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

---

풀이과정

• 정점과 간선이 주어졌으므로 인접 리스트와 DFS를 사용하여 탐색하였습니다.
• 방향이 없으므로 양방향을 가집니다.

 for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        //방향 없는 그래프 -> 쌍방향
        arr[u].push_back(v);
        arr[v].push_back(u);
    }

• 현재 정점에서 연결되어 있는 정점을 탐색하며 방문하지 않는 경우 DFS 탐색을 진행합니다.
• 하나의 DFS가 끝나게 되면 하나의 연결 요소를 구할 수 있습니다.
• 주어진 정점들을 DFS를 사용하여 완전 탐색하면 됩니다.

  for(int i=1;i<=n;i++){
        if(check[i]==false){
            //방문안했으면 dfs를 돈다
            dfs(i);
            //한번 돌면 하나의 연결요소 내를 전부 돈 것
            answer++;
        }
    }

---

전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;
bool check[1001];
vector<int> arr[1001]; //인접리스트
int n,m;
void dfs(int curr){
    check[curr]=true;//현재 위치 방문
    for(int i=0;i<arr[curr].size();i++){ //arr[1] = 2,5
        int next = arr[curr][i];
        if(check[next]==false){
            //방문안했더라면 dfs
            dfs(next);
        }
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        //방향 없는 그래프 -> 쌍방향
        arr[u].push_back(v);
        arr[v].push_back(u);
    }
    // dfs(1);
    // dfs(2);
    // dfs(3);
    int answer = 0;
    for(int i=1;i<=n;i++){
        if(check[i]==false){
            //방문안했으면 dfs를 돈다
            dfs(i);
            //한번 돌면 하나의 연결요소 내를 전부 돈 것
            answer++;
        }
    }
    cout<<answer;



    return 0;
}