Cod sursa(job #3249452)

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

void dfsHelper(const std::vector<std::vector<int>>& 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,m;

    in >> n >> m;
    
    std::vector<std::vector<int>> adjacencyList(n+1, std::vector<int>());
    std::vector<bool> visited(n+1, false);
    
    for(int 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;
}