Cod sursa(job #1512243)

Utilizator Maria98BMaria Monica Maria98B Data 27 octombrie 2015 20:21:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 100001;
vector<int>a[NMAX];
bool viz[NMAX];

void dfs( int n );

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

    int n, m, u, v, rez=0;
    fin >> n >> m;

    for ( int i=1; i<=m; i++ ) {
        fin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }

    for ( int i=1; i<=n; i++ )
        if ( viz[i]==0 ) {
            dfs(i);
            rez++;
        }
    fout << rez;
    return 0;
}

void dfs( int n )
{
    viz[n] = 1;
    for ( int i=0; i<(int)a[n].size(); i++ )
        if ( viz[a[n][i]] == 0 )
            dfs(a[n][i]);
}