Cod sursa(job #2202546)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 9 mai 2018 01:20:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>
#include <deque>
#define NMAX 100005
#define pb push_back
using namespace std;

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

int n,m;
vector<int>G[NMAX];
bool viz[NMAX];

void read_data(int &n, int &m){
    f >> n >> m;
    for(int i = 1; i<=m; i++){
        int x, y;
        f >> x >> y;
        G[x].pb(y);
        G[y].pb(x);
    }
}

void dfs(vector<int> G[], int src){
    viz[src] = true;
    for(int i = 0; i<G[src].size(); i++){
        if(!viz[G[src][i]]){
            dfs(G, G[src][i]);
        }
    }
}

int conex_comp(vector<int>G[]){
    int nrc = 1;
    dfs(G, 1);
    for(int i = 1; i<=n; i++){
        if(!viz[i]){
            nrc++;
            dfs(G, i);
        }
    }
    return nrc;
}

int main(){
    read_data(n, m);
    g << conex_comp(G);
    return 0;
}