Cod sursa(job #1347982)

Utilizator bogobatBerbece Daniel bogobat Data 19 februarie 2015 13:33:36
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct nod{ int n; nod *next;};
nod *graf[10009];
int n,m;
bool viz[10009];
int cnt;

void adaugare(int x, int z){
   nod *o=new nod;
   nod *p=new nod;
   p->n=x; p->next = graf[z]; graf[z]=p;
   o->n=z; o->next = graf[x]; graf[x]=o;
}

void DFS(int z){

viz[z]=1;
nod *i;
for(i=graf[z];i!=NULL;i=i->next){ if(!viz[i->n]) DFS(i->n);}

}
int main()
{   int x,z;
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>z;
        adaugare(x,z);
    }
    for(int i=1;i<=n;i++){if(!viz[i]) cnt++, DFS(i);}
    g<<cnt;
    return 0;
}