Cod sursa(job #2346121)

Utilizator Robys01Robert Sorete Robys01 Data 17 februarie 2019 11:01:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <vector>
#define pb push_back
#define NMAX 100005
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

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


void citire(){
    fin>>n>>m;
    for(; m; m--){
        int i, j; fin>>i>>j;
        A[i].pb(j);
        A[j].pb(i);
    }
}

void DFS(int x){
    viz[x] = true;
    for(int i=0; i<A[x].size(); i++){
        if(!viz[A[x][i]])
            DFS(A[x][i]);
    }
}


int main(){
    citire();

    for(int i=1; i<=n; i++){
        if(!viz[i]){
            m++;
            DFS(i);
        }
    }
    fout<<m;

    return 0;
}