백준)11724-연결 요소의 개수

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

11724번: 연결 요소의 개수

문제

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

입력

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

출력

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

풀이

방향성이 없는 그래프에서는 벡터에 양방향으로 입력받아주어 가중치 유무를 확인해주는 방법이 일반적이어서 벡터를 이용하여 구현하였다.

양방향으로 값을 입력 받아준후 DFS를 반복하여 이미 방문한 정점은 걸러주는 식으로 하여 연결돼있는 정점 끝까지 방문한 다음 끝나면 개수를 +1 해주었다.

#include<iostream>
#include<vector>
using namespace std;
int N ,M;
 
vector<int> a[1001];
int visited[1001];
 
 
 
 
void search(int n) {
 
    int i;
    visited[n] = 1;
 
        for( i = 0 ; i < a[n].size() ; i++) {
 
            if( visited[ a[n][i] ] == 1)
                continue;
 
            search(a[n][i]);
 
        }
 
}
 
 
 
int main()
{
    int i,j;
    int ans = 0 ;
    cin >> N >> M;
 
  int x,y;
    
    for( i = 0 ; i< M ;i++)    {
        cin >>  x >> y;
 
        a[x].push_back(y);
        a[y].push_back(x);
    }
 
 
 
    for( i = 1 ; i<= N ;i++) {
 
        if(visited[i] == 0 ) {
            search(i);
 
          ans++;
        
        }
 
    }
 
 
cout << ans;
 
 
 
    return 0;
}