Cod sursa(job #276743)

Utilizator silaghi_raulSzilagyi Raul Razvan silaghi_raul Data 11 martie 2009 12:26:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
int N,M,viz[100001];
typedef struct Nod
{
  int k;
  struct Nod *urm;
}*pNod;
pNod v[100001];
void add(pNod &dest,int x)
{
  pNod p;
  p = new Nod;
  p->k=x;
  p->urm=dest;
  dest=p;
}

void citire()
{
  int i,x,y;
  FILE *in = fopen("dfs.in","rt");
  fscanf(in,"%d %d",&N,&M);
  for(i=1;i<=M;i++)
  {
    fscanf(in,"%d %d",&x,&y);
    add(v[x],y);
    add(v[y],x);
  }
  fclose(in);
}
void df(int nod)
{
  pNod p;
  viz[nod]=1;
  for(p=v[nod];p!=NULL;p=p->urm)
  if(!viz[p->k]) df(p->k);
}
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);
  fclose(out);
  return 0;
}