Cod sursa(job #2758596)

Utilizator lahayonTester lahayon Data 11 iunie 2021 14:09:39
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph){

    visited[node] = 1;
    for(auto vecin : graph[node])
        if(!visited[vecin])
            dfs(vecin, visited, graph);
}


int main()
{
    ifstream cin("dfs.in");
    ofstream cout("dfs.out");
         
    int N, M, S = 0, x, y;
    cin >> N >> M;

    vector<vector<int>> graph(N, vector<int>{});
    vector<bool> visited(N, false);

    for(int i = 0; i < M; ++i){

        cin >> x >> y;
        graph[--x].push_back(--y);
    }

   for(int i = 0; i < N; ++i)
        if(!visited[i]){
            ++S;
            dfs(i, visited, graph);
        }

    cout << S;
   

    cin.close();
    cout.close();

    return 0;
}