Cod sursa(job #1604143)

Utilizator gerd13David Gergely gerd13 Data 17 februarie 2016 23:42:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <algorithm>
#define pb push_back

using namespace std;

const int NMAX = 200005 ;
const int INF = 0x3f3f3f3f ;

vector <int> V[NMAX] ;

int use[NMAX], N, M ;

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

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()
{
    fin >> N >> M ;

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

    int cnt = 0 ;

    for(int i = 1 ; i <= N ; ++ i)

        if(use[i] == 0)
        {cnt ++ ;
        DFS(i) ;
        }

    fout << cnt << '\n' ;

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