Cod sursa(job #2751051)

Utilizator Mihai_BarbuMihai Barbu Mihai_Barbu Data 13 mai 2021 23:58:13
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 2;

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

void dfs(int node, vector<int>& vis, vector<int> adj[]) {
    vis[node] = 1;

    for (auto neigh : adj[node]) {
        if (vis[neigh] == 0) {
            dfs(neigh, vis, adj);
        }
    }
}

int main() {
    int N, M;

    fin >> N >> M;

    vector<int> adj[NMAX];

    int i, x, y;
    
    for (i = 1; i <= M; ++i) {
        fin >> x >> y;

        adj[x].push_back(y);
    }

    vector<int> vis(N + 1, 0);

    int res = 0;
    for (i = 1; i <= N; ++i) {
        if (vis[i] == 0) {
            res++;

            dfs(i, vis, adj);
        }
    }

    fout << res << "\n";

    return 0;
}