Cod sursa(job #2659144)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 15 octombrie 2020 21:44:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "dfs.in" );
ofstream fout( "dfs.out" );

const int NMAX = 100005;

int N, M;
vector <int> Ad[NMAX];
int comp[NMAX];
int nr_c;

void Dfs( int nod, int nrc ) {
    int w;
    comp[nod] = nrc;

    for( int i = 0; i < Ad[nod].size(); ++i ) {
        w = Ad[nod][i];
        if( comp[w] == 0 ) Dfs( w, nrc );
    }
}

void Read()
{
    fin >> N >> M;

    for( int i = 1; i <= M; ++i ) {
        int a, b;

        fin >> a >> b;

        Ad[a].push_back( b );
        Ad[b].push_back( a );
    }
}

void Do()
{
    for( int i = 1; i <= N; ++i )
        if( comp[i] == 0 ) { ++nr_c; Dfs( i, nr_c ); }

    fout << nr_c << '\n';
}


int main()
{
    Read();
    Do();

    return 0;
}