Cod sursa(job #2594748)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 6 aprilie 2020 16:25:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda laborator_7_sd_313cab Marime 0.83 kb
#include <fstream>
#include <vector>

#define NMAX 100001

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");


void DFS(int node, vector <int> edge_list[NMAX], bool visited[NMAX]) {
    visited[node] = 1;
    for(int i = 0 ; i < edge_list[node].size() ; i++) {
        if (visited[edge_list[node][i]] == 0) {
            DFS(edge_list[node][i], edge_list, visited);
        }
    }
}

int main()
{
    int N, M, x, y;
    vector <int> edge_list[NMAX];

    f>>N>>M;
    for (int i = 0 ; i <  M ; i++) {
        f>>x>>y;
        edge_list[x].push_back(y);
        edge_list[y].push_back(x);
    }

    int comp_conex = 0;
    bool visited[NMAX];
    for (int i = 1 ; i <= N ; i++) {
        if (visited[i] == 0) {
            comp_conex++;
            DFS(i, edge_list, visited);
        }
    }
    g<<comp_conex;
    return 0;
}