Cod sursa(job #256981)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 12 februarie 2009 16:53:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream.h>
#include <fstream.h>

#define IN "dfs.in"
#define OUT "dfs.out"
#define maxx 100002

ifstream fin(IN);
ofstream fout(OUT);

int n,m;
struct lista
{
 int nod;
 lista *urm;
}*g[maxx];
int u[maxx];

void citire();
void add(int x,int y);
void df(int nod);
void comp_con();
void afis()
{
 int i;
 lista *q;

 for(i=1;i<=n;i++)
 {
  q=g[i];
  fout<<i<<"   ";
  while(q)
  {
   fout<<q->nod<<" ";
   q=q->urm;
  }
  fout<<endl;
 }
}

int main()
{
 citire();
  fin.close();

 comp_con();

 fout<<endl;
 
 //afis();

 fout.close();
return 0;
}

void citire()
{
 int i;
 int x,y;

 fin>>n>>m;

 for(i=1;i<=m;i++)
 {
  fin>>x;
  fin>>y;
  add(x,y);
  add(y,x);
 }
}

void add(int x,int y)
{
 lista *q;

 q=new lista;

 q->nod=y;
 q->urm=g[x];
 g[x]=q;
}

void df(int nod)
{
 lista *p;

 u[nod]=1;

 for(p=g[nod];p!=NULL;p=p->urm)
  if(!u[p->nod])
   df(p->nod);
}

void comp_con()
{
 int i;
 int v=0;

 memset(u,0,sizeof(u));

 for(i=1;i<=n;i++)
  if(!u[i])
  {
   df(i);
    v++;
  }
  fout<<v;
}