Cod sursa(job #160460)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 15 martie 2008 21:41:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
FILE*fin=fopen("dfs.in","r");
FILE*fout=fopen("dfs.out","w");
#define maxn 100001
struct nod{int inf;nod*urm;};
nod *ad[maxn],*q;
int used[maxn],n,m;
void rec(int nd)
{
  int ndc;
  nod *z;
  used[nd]=1;
  z=ad[nd];
  while(z)
  {
    ndc=z->inf;
    if(!used[ndc]) rec(ndc);
    z=z->urm;
  }
}
int main()
{
  int rez=0,i,a,b;
  fscanf(fin,"%d%d",&n,&m);
  for(i=1;i<=n;i++)
  {
    used[i]=0;
    ad[i]=NULL;
  }
  for(i=1;i<=m;i++)
  {
    fscanf(fin,"%d%d",&a,&b);
    q=new nod;
    q->inf=b;
    q->urm=ad[a];
    ad[a]=q;
    q=new nod;
    q->inf=a;
    q->urm=ad[b];
    ad[b]=q;
  }
  fclose(fin);
  for(i=1;i<=n;i++)
    if(!used[i])
    {
      rez++;
      rec(i);
    }
  fprintf(fout,"%d",rez);
  fclose(fout);
  return 0;
}