Cod sursa(job #1044246)

Utilizator hrazvanHarsan Razvan hrazvan Data 29 noiembrie 2013 15:21:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>
#define N 100000

typedef struct{
    int nr,urm;
}lista;

FILE *in,*out;
lista v[2*N+1];
int ultim[N+1],vizitat[N+1];

void dfs(int n){
    int i;
    vizitat[n]=1;
    i=ultim[n];
    while(i>0){
        if(!vizitat[v[i].nr]){
            dfs(v[i].nr);
        }
        i=v[i].urm;
    }
    return ;
}

int main(){
    in=fopen("dfs.in","r");
    out=fopen("dfs.out","w");
    int i,nrc,n,m,x,y;
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(in,"%d%d",&x,&y);
        v[2*i-1].nr=x;
        v[2*i-1].urm=ultim[y];
        ultim[y]=2*i-1;
        v[2*i].nr=y;
        v[2*i].urm=ultim[x];
        ultim[x]=2*i;
    }
    nrc=0;
    for(i=1;i<=n;i++){
        if(!vizitat[i]){
            dfs(i);
            nrc++;
        }
    }
    fprintf(out,"%d",nrc);
    return 0;
}