Cod sursa(job #381127)

Utilizator catalina5catalina serban catalina5 Data 9 ianuarie 2010 10:51:49
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include<fstream>

using namespace std;

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

int viz[100002];
long n, m, nr;

struct nod{
    int info;
    nod * urm;
} *v[100002];

void add(int x, int y){
    nod *q=new nod;
    q->info=x;
    q->urm=v[y];
    v[y]=q;
}

void citire(){
    fin>>n>>m;
    int x, y;
    for(int i=0;i<m;i++){
        fin>>x>>y;
        add(x,y);
        add(y,x);
    }
}

void dfs(int x){
    for(nod *i=v[x];i;i=i->urm)
        if(!viz[i->info]){
            viz[i->info]=1;
            dfs(i->info);
        }
}

void parcurgere(){
    for(int i=0;i<n;i++)
        if(viz[i]==0){
            dfs(i);
            nr++;
        }
}

int main(){
    citire();
    parcurgere();
    fout<<nr;
    return 0;
}