Cod sursa(job #1599842)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 14 februarie 2016 14:15:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
using namespace std;
FILE *f1=fopen("dfs.in","r");
FILE *f2=fopen("dfs.out","w");
int n,m,nr,k,v[100005],i;
struct nod{
   int inf;
   nod *urm;
}*L[100005];
void adaugaresf(int val,nod *&vf){
    nod *q;
    q=new nod;
    q->inf=val;
    q->urm=vf;
    vf=q;
}
void citire(){
    int k,a,b;
    fscanf(f1,"%d %d",&n,&m);
    for (k=1;k<=n;k++)
        L[k]=0;
    for (k=1;k<=m;k++){
        fscanf(f1,"%d%d",&a,&b);
        adaugaresf(a,L[b]);
        adaugaresf(b,L[a]);
    }
    fclose(f1);
}
void dfs(int k){
    nod *q;
    q=L[k];
    v[k]=1;
    while(q!=0){
        if (v[q->inf]==0){
            dfs(q->inf);
        }
        q=q->urm;
    }
}
int main(){
    citire();
    for (i=1;i<=n;i++)
      if (v[i]==0)
      {
          nr++;
          dfs(i);
      }
    fprintf(f2,"%d",nr);
    fclose(f2);
    return 0;
}