Cod sursa(job #1459565)

Utilizator BaweeLazar Vlad Bawee Data 10 iulie 2015 11:22:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <vector>
#include <fstream>
#include <iostream>


using namespace std;


int N, M, count = 0;
vector< vector<int> > g;
vector<bool> visited;

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



void read(){

    in >> N >> M;

    for(int i = 0; i <= N; ++i){
        vector<int> v;
        g.push_back(v);
    }

    visited.resize(N+1);

    int x, y;

    for(int i = 0; i < M; ++i){
        in >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}


void DFS(int u){

    visited[u] = true;
    for(unsigned int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if(visited[v] == false)
            DFS(v);
    }

}


void ComponenteConexe(){

    for(int i = 1; i <= N; ++i){
        if(visited[i] == false){
            count++;
            DFS(i);
        }
    }
}


int main(){

    read();
    ComponenteConexe();
    out << count;
}