Cod sursa(job #3317125)

Utilizator ninelcatelALEXANDRU-NICOLAS NEGRISAN ninelcatel Data 22 octombrie 2025 13:13:40
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>
std::fstream fin("dfs.in");
std::ofstream fout("dfs.out");

void dfs(std::vector<std::vector<int>>& adj, std::vector<bool>& visited,int src){
    visited[src]=true;
    for(auto &x:adj[src]){
        if(!visited[x]){
            dfs(adj,visited,x);
        }
    }
}

int main(){
    int n,m;
    fin>>n>>m;
    std::vector<std::vector<int>> adj(n+1);
    for(int i=0;i<m;i++){
        int x,y;
        fin>>x>>y;
        adj[x].push_back(y);
    }
    std::vector<bool> visited(n+1,false);
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!visited[i])
            {
                dfs(adj,visited,i);
                ++cnt;
            }
    }
    fout<<cnt<<"\n";
    fin.close();
    fout.close();
}