Cod sursa(job #276722)

Utilizator Mr.AndersonRazvan Birsan Mr.Anderson Data 11 martie 2009 12:21:51
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<stdio.h>
//int a[1000][1000];
int viz[100000],N,M;
typedef struct Pnod
{
  int vec;
  struct nod *urm;
}*nod;
nod v[100000];
void add(nod *p,int x)
{
  nod q= new nod;
  q->vec=x;
  q->urm=p;
  p=q;
}
void citire()
{
  int i;
  FILE * in=fopen("dfs.in","rt");
  fscanf(in,"%d %d", &N,&M);
  for(i=1;i<=M;i++)
  {
    int x,y;
    fscanf(in,"%d %d",&x,&y);
    add(v[x],y);
    add(v[y],x);
  }
  fclose(in);
}
void df(int st)
{
   nod p;
   int i;
   viz[st]=1;
   for(p=v[st];p!=NULL;p=p->urm)
   if(viz[p->x]==0)df(p->x);
}
int main()
{
  int i,nr=0;
  citire();
  for(i=1;i<=N;i++)
  if(!viz[i]){df(i);nr++;}
  FILE *out=fopen("dfs.out","wt");
  fprintf(out,"%d",nr);
  return 0;
}