Cod sursa(job #3246648)

Utilizator antonio.grGrigorascu Andrei Antonio antonio.gr Data 3 octombrie 2024 21:14:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <vector>
#include <fstream>
#include <unordered_map>

using namespace std;

int N, M;
const int NMAX = 100005;

vector<bool> visited(NMAX, false);

unordered_map<int, vector<int>> graph;

void dfs(int source){

    visited[source] = true;

    for(auto v : graph[source]){

        if(!visited[v]){
            dfs(v);
        }
    }
}

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

int main(){

    fin >> N >> M;
    int count = 0;
    for(int i = 0; i < M; i++){
        int x, y;
        fin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);

    }

    for(int i = 1; i <= N; i++){
        if(!visited[i]){
            count++;
            dfs(i);
        }
    }
    fout << count;
    return 0;
}