Cod sursa(job #1831002)

Utilizator aditzu7Adrian Capraru aditzu7 Data 17 decembrie 2016 12:13:49
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <iostream>
using namespace std;
FILE*f=fopen("dfs.in","r");
FILE*g=fopen("dfs.out","w");
int i,y,x, n,m,viz[100001];
struct nod{
int inf;
nod *urm;

}*v[1000001],*c;

void adaugare(nod *&prim,int x){
    nod *nou;
    nou=new nod;
    nou->inf=x;nou->urm=NULL;
    if(prim==NULL) prim=nou;
    else {nou->urm=prim,prim=nou;}
}
void DF(int i,int x){
  viz[i]=x;
  nod *p;
  for(p=v[i];p!=NULL;p=p->urm)
    {if(viz[p->inf]==0) DF(p->inf,x);
    }
}
int main()
{
fscanf(f,"%d%d%d",&n,&m);
for(i=1;i<=m;i++){

fscanf(f,"%d%d",&x,&y);
   adaugare(v[x],y);
adaugare(v[y],x);


}
 x=1;
for(i=1;i<=n;i++)if(viz[i]==0) DF(i,x);
else x++;
fprintf(g,"%d",x);
    fclose(f);
    fclose(g);

    return 0;
}