Cod sursa(job #288738)

Utilizator gggbbbyyyDarkMan gggbbbyyy Data 26 martie 2009 08:22:41
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<iostream.h>
#include<fstream.h>

struct nod
{
  int x;
  nod *nx;
};

nod *v[200000],*q;
  int viz[200000];
  long n,m,i,x,y,w;

void df(int x)
{
  viz[x]=1;
  q=v[x];
  while(q->nx!=NULL)
    {
      if(viz[q->x]==0)
      df(q->x);
      q=q->nx;
    }
}

int main()
{
  ifstream f("dfs.in");
  ofstream g("dfs.out");
  f>>n>>m;
  for(i=1;i<=n;i++)
    {
      v[i]->nx=NULL;
      viz[i]=0;
    }
  for(i=1;i<=m;i++)
    {
      f>>x>>y;
      q=new(nod);
      q->x=y;
      q->nx=v[x]->nx;
      v[x]->nx=q;
      q=new(nod);
      q->x=x;
      q->nx=v[y]->nx;
      v[y]->nx=q;

    }
  w=0;
  for(i=1;i<=n;i++)
    if(viz[i]==0)
      {
	w+=1;
	df(i);
      }
  g<<w;
  return(0);
}