#11724 연결요소의 개수

문제는 다음과 같다. (실버2)

'연결요소' 가 뭔지만 알면 어렵지 않은 문제였다. 그냥 dfs,bfs돌려서 한번 다 돌았으면 개수를 한개 추가해주면 되는거였다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

vector<vector<int>> a(1001,vector<int>(1001,0));
int N,M,V;
int check[1001];
queue<int> q;
void reset(){
  for(int i=0;i<=N;i++){
    check[i]=0;
  }
}

void bfs(int x){
  q.push(x);
  check[x]=1;
  while(!q.empty()){
    //cout<<q.front()<<" ";
    x=q.front();
    q.pop();
    for(int i=1;i<=N;i++){
      if(a[x][i]==1&&check[i]==0){
        q.push(i);
        check[i]=1;
      }
    }
  }
}

int SUM(){
  int sum=0;
  for(int i=1;i<=N;i++){
    sum+=check[i];
  }
  return sum;
}

int main()
{
  int cc=0;
  int idx=0;  
  cin>>N>>M;
  while(M--){
    int n1,n2;
    cin>>n1>>n2;
    a[n1][n2]=1;
    a[n2][n1]=1;
  }
  reset();

  for(int i = 1; i <= N; i++){
    if (!check[i]){
      bfs(i);
      cc++;
    }
  }
  cout << cc;
}

코드는 위와 같다.

 

1. 배운것

-bfs에서는 queue를 이용하여 구현한다.

-위와 같이 vector를 선언하면, a[n1][n2]=1; 과 같이 접근하여 값을 대입하는것이 가능하다.

-백준 문제에 주어지는 <입력>을 잘 보고 배열의 크기를 잘 정해야한다.

  이 문제에서는 N과 M에 크기 제한이 있어서 위와 같이 vector의 크기를 1001로 맞추어 선언하였다.

  (그렇지 않으면 런타임 에러 Out of Bounds 뜨거나 틀림)