Cod sursa(job #1710854)

Utilizator IuliaRisteaRistea Iulia IuliaRistea Data 29 mai 2016 21:13:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <stdio.h>
#define NMAX 100010
using namespace std;
struct lista
{
    int nod;
    lista *urm;
}*g[NMAX];
int n,m,visit[NMAX],i,nr;
FILE *f1=fopen("dfs.in","r"),*f2=fopen("dfs.out","w");
void adauga(int i,int j)
{
   lista *aux=new lista;
   aux->nod=i;
   aux->urm=g[j];
   g[j]=aux;
}
void df(int nod)
{
    lista *p;
    visit[nod]=1;

    for(p=g[nod];p;p=p->urm)
        if(!visit[p->nod])df(p->nod);
}

int main()
{
  fscanf(f1,"%d%d",&n,&m);
  for(i=1;i<=m;i++){int x,y;fscanf(f1,"%d%d",&x,&y);adauga(x,y);adauga(y,x);}
  for(i=1;i<=n;i++)
  if(!visit[i]){nr++;df(i);}
  fprintf(f2,"%d",nr);
  return 0;
}