Cod sursa(job #1610964)

Utilizator gerd13David Gergely gerd13 Data 23 februarie 2016 20:57:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>


using namespace std ;

const int NMAX = 100005 ;

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

int N, M, use[NMAX];
vector <int> V[NMAX] ;
queue <int> Q ;


void DFS(int nod)
{
    use[nod] = 1 ;
    for(vector <int>::iterator it = V[nod].begin(); it != V[nod].end() ; ++ it)
        if(use[*it] == 0)
        {
            use[*it] = 1 ;
            DFS(*it) ;
        }
}


int main()
{

    int cnt = 0 ;

    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(use[i] == 0)
        {
            DFS(i) ;
            cnt ++ ;
        }

    fout << cnt << '\n' ;

    fin.close() ;
    fout.close();
    return  0 ;
}