Cod sursa(job #3122484)

Utilizator Claudiu_MogoMogodeanu Claudiu Claudiu_Mogo Data 19 aprilie 2023 13:30:53
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;

static constexpr int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005

// n = numar de noduri, m = numar de muchii/arce
int n, m;

// adj[node] = lista de adiacenta a nodului node
// exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
vector<int> adj[NMAX];

void read_input() {
    ifstream fin("dfs.in");
    fin >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
        fin >> x >> y; // arc (x, y)
        adj[x].push_back(y);
    }
    fin.close();
}

void DFS(int src, vector<int> &visited) {
    for (int i = 0; i < adj[src].size(); i++) {
        if (visited[adj[src][i]] == 0) {
            visited[adj[src][i]] = 1;
            DFS(adj[src][i], visited);
        }
    }
}

int main() {
    ofstream fout("dfs.out");

    read_input();
    vector<int> visited(n + 1, 0);
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            DFS(i, visited);
            count++;
        }
    }

    fout << count;
    fout.close();
    return 0;
}