Cod sursa(job #220390)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 10 noiembrie 2008 18:00:12
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
using namespace::std;
int n,m,viz[100000];
ifstream in("dfs.in");
ofstream out("dfs.out");
typedef struct nod
{int x;nod* a;} *pNod;
pNod v[100000];
void add(pNod &dest,int val)
{pNod p;
p=new nod;
p->x=val;
p->a=dest;
dest=p;}
void citire()
{int x,y;
in>>n;in>>m;
for(int i=1;i<=m;i++)
{
in>>x;in>>y;
add(v[x],y);add(v[y],x);}}
void dfs(int d)
{pNod p;
viz[d]=1;
for(p=v[d];p!=NULL;p=p->a)
 if(viz[p->x]) {viz[p->x]=1;dfs(p->x);}
 }


int main()
{citire();
int nrc=0;
for(int i=1;i<=n;i++) if(!viz[i]) {nrc++;dfs(i);}
out<<nrc;


      return 0;
}