Cod sursa(job #3123528)

Utilizator ivddabDabelea Ioana-Viviana ivddab Data 24 aprilie 2023 13:07:09
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

vector<bool> been_there;
vector<vector<int>> adj;

void dfs(int node) {
    been_there[node] = true;

    for(int nodes : adj[node]) {
        if(!been_there[nodes])
            dfs(nodes);
    }
}

int main() {
    int n, m, x, y;
    FILE *f = fopen("dfs.in", "r");
    fscanf(f, "%d%d", &n, &m);
    adj.resize(n + 1);

    for(int i = 0; i < m; i++) {
        fscanf(f, "%d%d", &x, &y);
        adj[x].push_back(y);
    }
    fclose(f);

    been_there.resize(n + 1, false);
    int result = 0;
    for(int i = 1; i <= n; i++) {
        if(!been_there[i]) {
            result++;
            dfs(i);
        }
    }

    f = fopen("dfs.out", "w");
    fprintf(f, "%d\n", result);
    return 0;
}