Cod sursa(job #188093)

Utilizator me_andyAvramescu Andrei me_andy Data 6 mai 2008 19:44:32
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include<fstream.h>
#define max 1000

 ifstream f("dfs.in");
 ofstream g("dfs.out");
 int viz[max],a[max][max],cont,n,m,i,x,y,nr[max];


void dfs(int k)
{       int i;
 if(viz[k])
  return;
 viz[k]=cont;
 for(i=1;i<=nr[k];i++)
  if(!viz[a[k][i]])
   dfs(a[k][i]);
}

int main()
{
 f>>n>>m;
 for(i=1;i<=m;i++)
 {
  f>>x;
  f>>y;
  a[x][++nr[x]]=y;
  a[y][++nr[y]]=x;
 }
 for(i=1;i<=n;i++)
  if(!viz[i])
  {
   cont++;
   dfs(i);
  }
  g<<cont;
  f.close();
  g.close();
  return 0;
}