[백준/C++] 11724번_연결 요소의 개수

15593 단어 백준GraphDFSDFS

문제는 다음과 같습니다.

연결 요소의 개수를 구하는 방법은 다음과 같습니다.

한 정점으로부터 dfs를 수행하였을 때 연결된 그래프가 한 개의 연결요소가 됩니다.
그리고 위의 그래프에서 포함된 정점을 제외시키고, 남은 점들에서 다시 dfs를 수행하면 됩니다.

정점이 고립?되어 있어도 이는 하나의 연결요소가 됩니다.

저는 연결요소의 개수를 변수 res로 계산하였고,
모든 정점에 대해서 dfs를 수행하였습니다.
❗️단, dfs를 수행하기 위해서는 시작 정점이 'ch[정점]==0' 이어야 합니다.❗️ (➡️이미 다른 그래프의 연결요소에 포함되어있지 않아야 합니다.)

전체 코드는 다음과 같습니다.

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

int n, m, res=0;
vector<int> v[1001];
int ch[1001]={0, };

void DFS(int k){
  for(int i=0; i<v[k].size(); i++){
    if(ch[v[k][i]]==0){
      ch[v[k][i]]=1;
      DFS(v[k][i]);
    }
  }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;

    for(int i=0; i<m; i++){
      int a, b; cin>>a>>b;
      v[a].emplace_back(b); v[b].emplace_back(a);
    }

    ch[1]=0; DFS(1); res+=1;
    for(int i=2; i<=n; i++){
      if(ch[i]==0){
        ch[i]=1;
        DFS(i);
        res++;
      }
    }

    cout<<res<<"\n";
    return 0;
}

2/16 수요일 복습)

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

 vector<int> v[1001];
 int ch[1001]={0, };
 int n, m;

 void DFS(int k){
   for(int i=0; i<v[k].size(); i++){
     if(ch[v[k][i]]==0){
       ch[v[k][i]]=1;
       DFS(v[k][i]);
     }
   }
 }

 int main() {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);

     cin>>n>>m;
     for(int i=0; i<m; i++){
       int t1, t2; cin>>t1>>t2;
       v[t1].emplace_back(t2); v[t2].emplace_back(t1);
     }

     int res=0;
     // DFS수행
     for(int i=1; i<=n; i++){
       if(ch[i]==0){
         ch[i]=1;
         DFS(i);
         res++;
       }
     }

     cout<<res<<endl;
     return 0;
 }

좋은 웹페이지 즐겨찾기