Cod sursa(job #3249456)

Utilizator mihaidanaila11Danaila Mihai Teodor mihaidanaila11 Data 16 octombrie 2024 15:01:08
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <iostream>
#include <vector>

void dfsHelper(const std::vector<std::vector<long long>>& adjList, std::vector<bool>& visited, int s){
    visited[s] = true;

    for(const int& node : adjList[s]){
        if(!visited[node])
            dfsHelper(adjList, visited, node);
    }
}

int dfs(){
    std::ifstream in("dfs.in");
    int n;
    long long m;

    in >> n >> m;
    
    std::vector<std::vector<long long>> adjacencyList(n+1, std::vector<long long>());
    std::vector<bool> visited(n+1, false);
    
    for(long long i=0; i<m; i++){
        int node1, node2;

        in >> node1 >> node2;
        adjacencyList[node1].push_back(node2);
    }

    in.close();
    
    int conexCnt = 0;

    for(int i=1; i<n+1; i++){
        if(!visited[i]){
            dfsHelper(adjacencyList, visited, i);
            conexCnt++;
        }   
    }

    return conexCnt;

}

int main(){
    std::ofstream out("dfs.out");
    out << dfs();

    return 0;
}