Cod sursa(job #544992)

Utilizator alexandru93moraru alexandru sebastian alexandru93 Data 2 martie 2011 16:02:22
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<fstream.h>
#define nmax=100010

ifstream f("dfs.in");
ofstream g("dfs.out");
long long n,m,viz[nmax];
struct nod{
int c;
nod *next;
};
nod *a[nmax];

void add(int x,int y){
nod *q=new nod;
q->c=y;
q->next=a[x];
a[x]=q;
};

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

void dfs(int j){
viz[j]=1;
nod *q=new nod;
q=a[j];
while(q){
if(viz[q->c]==0)
dfs(q->c);
q=q->next;
}
}

int main(){
int k=0;
citire();
for(int i=1;i<=n;i++)
if(viz[i]==0)
dfs(i),++k;
g<<k<<'\n';
g.close();
return 0;
}