Cod sursa(job #1986129)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 28 mai 2017 13:00:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <vector>
#include <fstream>

#define ll long long
#define pb push_back

using namespace std;

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

const int NLIM = 1e5 + 10;

int N, M;
vector< int > graph[NLIM];
int dfs[NLIM];


void f( int nod )
{
    dfs[nod] = 1;
    for( int j = 0; j < graph[nod].size(); ++j )
    {
        int nnod = graph[nod][j];
        if( !dfs[nnod] )
            f( nnod );
    }
}

int main()
{
    fin >> N >> M;
    for( int i = 0; i < M; ++i )
    {
        int x, y;
        fin >> x >> y;
        graph[x].pb( y );
        graph[y].pb( x );
    }

    int er = 0;
    for( int i = 1; i <= N; ++i )
    {
        if( !dfs[i] )
        {
            ++er;
            f( i );
        }
    }

    fout << er;
    return 0;
}