11724-接続要素数-DFS

質問する

質問リンク:https://www.acmicpc.net/problem/11724

ポリシー

時間で十分です.問題で要求される接続要素の個数は,単純に相互に接続されていないグループの個数と考えられる.やはり入力と出力を分析して、問題をよく読みます.

接続関係はDFSのみで理解できます.

コード#コード#

#include<bits/stdc++.h>

using namespace std;


int N, M;
int a[1001][1001];
bool ch[1001] = {false,};
int cnt = 0;

void DFS(int v){

    for(int i=1; i<=N; i++){
        if(!ch[i] && a[v][i] == 1){
            ch[i] = true;
            DFS(i);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N >> M;
    int ta, tb;
    for(int i=1; i<=M; i++){
        cin >> ta >> tb;
        a[ta][tb] = 1;
        a[tb][ta] = 1;
    }

    for(int i=1; i<=N; i++){
        if( !ch[i] ){
            ch[i] = true;
            DFS(i);
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

感想

接続要素という用語が何なのか分かりませんが、inputとoutputを比較することで、どういう意味なのか分かりました.やはり問題を分析することが一番重要だ.