Cod sursa(job #1358717)

Utilizator gerd13David Gergely gerd13 Data 24 februarie 2015 19:22:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <algorithm>





using namespace std ;

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

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

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


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

        for(int i = 0 ; i < V[nod].size() ; ++ i)
            if(!use[V[nod][i]])
        {
            use[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(!use[i])
    {
        sol ++ ;
        DFS(i) ;
    }

    fout << sol << '\n' ;

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