Cod sursa(job #1592214)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 7 februarie 2016 11:45:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>

using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int m;
struct nod{
    int info;
    nod *next;
};
struct nod *v[100005];
int n,viz[100005],t;
//inserare sfarstit
nod* inserare(nod *p,int x){
    nod* elem=new nod;
    elem->info=x;
    elem->next=NULL;
    if(p==NULL){
        return elem;
    }
    else{
        nod *parcurg=p;
        while(parcurg->next!=NULL)
            parcurg=parcurg->next;
        parcurg->next=elem;
        return p;
    }
}
nod* inserare_inceput(nod *p,int x){
    nod *elem=new nod;
    elem->info=x;
    elem->next=p;
    return elem;
}
void DFS(int x){
    if(viz[x]==0){
        viz[x]=++t;
        nod *parcurg=v[x];
        while(parcurg){
            DFS(parcurg->info);
            parcurg=parcurg->next;
        }
    }
}
void citire(){
    int l;
    cin>>n>>l;
    for(int i=1;i<=n;i++)
        v[i]=NULL;
    int x,y;
    for(int i=1;i<=l;i++){
        cin>>x>>y;
        v[x]=inserare_inceput(v[x],y);
        v[y]=inserare_inceput(v[y],x);
    }
}
int main(){
    citire();
    int i;
    for(i=1;i<=n;i++){
        if(viz[i]==0){
            DFS(i);
            ++m;
        }
    }
    cout<<m<<'\n';

    return 0;
}