[DFS] BOJ 11724 연결 요소의 개수

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

문제 해결 알고리즘

 

모든 노드를 탐색하는데 탐색할 때 연결된 노드들을 전부 DFS로 탐색해준다. 탐색이 안 된 곳(cc[i]가 0인 곳)을 계속해서 DFS로 탐색해주면서 연결요소마다 번호를 매겨준다. 마지막에 그 연결요소의 마지막 번호를 출력한다.

 

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int cc[1001];
vector<int> graph[1001];
int cnt = 1;

void find_cc(int x){
  for(int i=0;i<graph[x].size();i++){
    if(cc[graph[x][i]] == 0){
      cc[graph[x][i]] = cnt;
      find_cc(graph[x][i]);
    }
  }
}

int main(){
  int N, M; cin >> N >> M;

  int u, v; 
  for(int i=0;i<M;i++){
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  for(int i=1;i<=N;i++){
    if(cc[i] == 0) {
      if(i == 1) cc[1] = cnt;
      find_cc(i);
      cnt++;
    }
  }

  cout << cnt - 1;
}