Cod sursa(job #2595072)

Utilizator arinaturcuArina Turcu arinaturcu Data 7 aprilie 2020 00:11:08
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda laborator_7_sd_313cab Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <queue>
#include <list>
#include <vector>

#define MAX_NODES 100010
  
using namespace std;

void addEdge(vector<int> lg[], int u, int v) { 
    lg[u].push_back(v);  
} 

void dfs(vector<int> lg[], int node, int *visited) {
    visited[node] = 1;
    
    for (auto x : lg[node]) {
        if (visited[x] == 0) {
            dfs(lg, x, visited);
        }
    }
}

void connected_components(vector<int> lg[], int N, int *visited, int *components) {
    for (int i = 1; i <= N; ++i) {
        if (visited[i] == 0) {
            (*components)++;
            dfs(lg, i, visited);
        }
    }
}
  
int main() { 
    ifstream in("dfs.in");
    ofstream out("dfs.out");

    int N, M;
    int sur, des, components = 0;

    in >> N >> M;

    vector<int> lg[N+1];
    int visited[N+1] = {0};

    for (int i = 0; i < M; ++i) {
        in >> sur >> des;
        addEdge(lg, sur, des);
    }

    connected_components(lg, N, visited, &components);

    out << components;

    in.close();
    out.close();
  
    return 0; 
}