[백준] 연결 요소의 개수 - C++

[Silver II] 연결 요소의 개수 - 11724

문제 링크

성능 요약

메모리: 5940 KB, 시간: 280 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제 설명

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

입력

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

출력

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

 

 

---

 

연결 요소가 뭔가 했는데, 연결되어 있는 그래프의 개수를 뜻한다.

즉, 1-3-5 그래프와 2-4-6 그래프가 있으면, 연결 요소는 2개.

1-3-2-5-4-6 으로 연결되어 있으면 1개.

위 이미지는 연결 요소가 2개이다.

 

출처 - https://velog.io/@polynomeer/%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CConnected-Component

#include <iostream>

using namespace std;

int graph[1001][1001] = {0};
int visited[1001] = {0};

void dfs(int v)
{
  visited[v] = 1;

  for (int i = 1; i < 1001; i++)
  {
    if (graph[v][i] == 1 && visited[i] == 0)
      dfs(i);
  }
  return;
}

int main()
{
  int N, M;
  cin >> N >> M;
  int answer = 0;
  while (M--)
  {
    int a, b;
    cin >> a >> b;
    graph[a][b] = 1;
    graph[b][a] = 1;
  }
  for (int i = 1; i <= N; i++)
  {
    if (visited[i] == 0)
    {
      dfs(i);
      answer++;
    }
  }
  cout << answer << endl;
  return 0;
}

dfs로 모든 node를 돌면서 visited에 없는 그래프의 개수를 찾았다. 즉, 시작한 노드의 개수 == 연결 요소의 개수

 

처음엔 조건을 잘못이해해서 정점이 3개면 1, 5, 10 이렇게 3개도 될 수 있는 줄 알고 헤맸는데, (1 ≤ u, v ≤ N, u ≠ v) 이 조건을 보면 정점이 3개일 땐 1, 2, 3 으로 된다는 걸 알 수 있다.