Cod sursa(job #1841648)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 5 ianuarie 2017 20:54:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,viz[NMAX],contor;
struct nod{
    int info;
    nod* urm;
}*v[NMAX];
nod* inserare_inceput(nod* p,int x){
    if(p==NULL){
        nod* elem=new nod;
        elem->info=x;
        elem->urm=NULL;
        return elem;
    }
    nod* elem=new nod;
    elem->info=x;
    elem->urm=p;
    return elem;
}
void citire(){
    f>>n>>m;
    int k,i,j;
    for(k=1;k<=m;k++){
        f>>i>>j;
        v[i]=inserare_inceput(v[i],j);
        v[j]=inserare_inceput(v[j],i);
    }
}
void DFS(int x){
    viz[x]=1;
    //g<<x<<' ';
    nod* parcurg=v[x];
    while(parcurg){
        if(viz[parcurg->info]==0)
            DFS(parcurg->info);
        parcurg=parcurg->urm;
    }
}
int main(){
    citire();
    for(int i=1;i<=n;i++){
        if(viz[i]==0){
            ++contor;
            DFS(i);
        }
    }
    g<<contor<<'\n';
    return 0;
}