Cod sursa(job #1501057)

Utilizator gerd13David Gergely gerd13 Data 12 octombrie 2015 22:59:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std ;

const int NMAX = 100005 ;

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

vector <int> V[NMAX] ;

int N, M, cnt, viz[NMAX];


void DFS(int nod)
{
    viz[nod] = 1 ;

    for(int i = 0 ; i < V[nod].size() ; ++ i)
        if(!viz[V[nod][i]])
    {
        viz[V[nod][i]] = 1 ;
        DFS(V[nod][i]) ;
    }
}

int main()
{

    fin >> N >> M ;

    for(int i = 1 ; i <= M ; ++ i)
    {
        int x, y ;
        fin >> x >> y ;
        V[x].push_back(y) ;
        V[y].push_back(x) ;
    }

    for(int i = 1 ; i <= N ; ++ i)
    if(!viz[i]){
        cnt ++ ;
        DFS(i) ;
    }

    fout << cnt << '\n' ;

    return  0 ;
}