Cod sursa(job #714617)

Utilizator StefanLacheStefan Lache StefanLache Data 15 martie 2012 21:41:28
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#include<stdlib.h>
struct nod
{
    int info;
    nod *adr_urm;
};
nod *v[200001];
int nrsol,viz[200001];
void DF(int i)
{
    viz[i]=1;
    while(v[i])
            {if(viz[v[i]->info]==0)
                DF(v[i]->info);
              v[i]=v[i]->adr_urm;
            }

}
void rez(int N)
{
    int i;
    for(i=1;i<=N;++i)
        if(viz[i]==0)
            {
                ++nrsol;
                DF(i);
            }
}
int main()
{
    FILE *f=fopen("dfs.in","rt");
    FILE *g=fopen("dfs.out","wt");
    int N,M,nr1,nr2,i;
    fscanf(f,"%i %i",&N,&M);
    while(!feof(f))
    {
        fscanf(f,"%i %i",&nr1,&nr2);
        nod *h=(nod *)malloc(1*sizeof(nod));
        h->info=nr2;
        h->adr_urm=v[nr1];
        v[nr1]=h;
    }
    rez(N);
    fprintf(g,"%i",nrsol);
    return 0;
}