Cod sursa(job #2437874)

Utilizator raidenjiAndrei raidenji Data 10 iulie 2019 16:33:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 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>

bool visited[100005];
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[100005];

    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;

    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);
        }
    }
}