Cod sursa(job #301495)

Utilizator bacerandreiBacer Andrei bacerandrei Data 8 aprilie 2009 11:35:09
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream.h>
#define max 1012
ifstream f("dfs.in");
ofstream g("dfs.out");

int n, m, sel[max], x, y, count = 0;


typedef struct nod
{
  int info;
  nod *urm;
} * pnod;
pnod v[max];


void add(pnod &dest, int val)
{
  pnod p;
  p = new nod;
  p->info = val;
  p->urm = dest;
  dest = p;
}


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


void dfs(int nd)
{
  pnod p;
  sel[nd] = 1;
    for(p = v[nd] ; p != NULL ; p = p->urm)
      if(!sel[p->info])
	dfs(p->info);
}



int main()
{
   read();
    for(int i = 1 ; i <= n ; i++)
      if(!sel[i])
       {
	 count++;
	 dfs(i);
       }
   g<<count;
  f.close();
  g.close();
 return 0;
}