[알고리즘 BFS & DFS 1] CONNECTEDCOMP

문제

---

정점의 번호가 1부터 N까지 존재하는 그래프 G가 존재하고, 어떠한 정점 집합 S={i, j, k,..} 끼리는 서로 간선으로 연결되어있으며, 그 이외의 정점 집합(S`)과는 연결되어있지 않을때, 집합 S로 그려지는 그래프를 그래프 G의 연결요소(Connected Component)라고 합니다. 만약 정점 집합 S와 S`의 합집합이 G의 정점의 전체일 경우, 그래프 G의 연결요소의 개수는 2개입니다. 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

 

입력

---

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

 

출력

---

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

 

예제 입력 1

5 4

1 2

3 4

3 5

4 5

예제 출력 1

2

 

예제 입력 2

5 6

1 2

1 5

2 4

3 4

3 5

4 5

예제 출력 2

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include<iostream>
 
#include<vector>
#include<algorithm>
using namespace std;
 
const int MAX = 100005;
vector <int> graph[MAX];
bool check[MAX];
 
int v, e;
int cc = 0;
 
void DFS(int node){
  
  check[node] = true;
  
  for(int i=0; i<graph[node].size(); i++){
    if(!check[graph[node][i]]){
      DFS(graph[node][i]);
    }
  }
  
}
 
int main(){
  
  cin>>v>>e;
  
  for(int i=1; i<=e; i++){
    int a, b;
    cin>>a>>b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  
  for(int i=1; i<=v; i++){
    if(!check[i]){
      DFS(i);
      cc++;
    }
  }
  
  printf("%d\n",cc);
  
  return 0;
}