Cod sursa(job #2437876)

Utilizator raidenjiAndrei raidenji Data 10 iulie 2019 16:35:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#define F 

using namespace std;

#ifdef IO
    #include <iostream>
    #define fin cin
    #define fout cout 
#endif

#ifdef F
    #include <fstream>
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");  
#endif

#include <vector>
#include <cstring>

int N, M, x, y;

int getNumberOfComponents(vector <int> G[]);
void DFS(vector <int> G[], int startNode, bool visited[]);

int main() {
    fin >> N >> M;
    vector <int> G[N + 5];

    for (int i = 1; i <= M; ++i) {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    fout << getNumberOfComponents(G);

#ifdef F
    fin.close();
    fout.close();
#endif
}

int getNumberOfComponents(vector <int> G[]) {
    int num = 0;
    bool visited[N + 5];
    memset (visited, false, sizeof visited);

    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            DFS(G, i, visited);
            num++;
        }
    }
    return num;
}

void DFS(vector <int> G[], int startNode, bool visited[]) {
    visited[startNode] = true;
    for (auto &it: G[startNode]) {
        if (!visited[it]) {
            DFS(G, it, visited);
        }
    }
}