Cod sursa(job #1712506)

Utilizator dcutitoiuCutitoiu Adrian-Nicolae dcutitoiu Data 2 iunie 2016 23:01:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

void DFS(int N, const vector<vector<int>> &adj, vector<bool> &visited){
    visited[N] = true;

    for(auto &x : adj[N]){
        if(visited[x] == false)
            DFS(x,adj,visited);
    }
}

int main(){

    int N, M, x, y;

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

    in >> N >> M;

    vector<vector<int>> adj(N+1);

    vector<bool> visited(N+1);

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

    int counter = 0;

    for(int i = 1; i <= N; i++){
        if(visited[i] == 0){
            counter++;
            DFS(i,adj,visited);
        }
    }

    out << counter;

    return 0;
}