Cod sursa(job #807692)

Utilizator IoanaMarMarussi Ioana IoanaMar Data 5 noiembrie 2012 15:33:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <string.h>
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

struct point{
int inf;
point *leg;
};

point *l[100005],*p;

bool sel[100005];
int n,m,x,y,i,nr;

void dfs (int x)
{
  point *poz;
  sel[x]=true;
  poz=new point;
  poz=l[x];

  while (poz)
  {
      if (!sel[poz->inf])
         dfs(poz->inf);
      poz=poz->leg;
  }
}

int main()
{
  f>>n>>m;
  memset(l,NULL,sizeof(l));
  for(i=1;i<=m;i++)
  {
      f>>x>>y;
      p=new point;
      p->inf=y;
      p->leg=l[x];
      l[x]=p;

      p=new point;
      p->inf=x;
      p->leg=l[y];
      l[y]=p;
  }
  for(i=1; i<=n; i++)
      if(!sel[i])
      {
          dfs(i);
          nr++;
      }
  g<<nr<<"\n";
return 0;
}