Cod sursa(job #714649)

Utilizator StefanLacheStefan Lache StefanLache Data 15 martie 2012 22:11:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<stdio.h>
#include<stdlib.h>
struct nod
{
    int info;
    nod *adr_urm;
};
nod *v[100001];
int nrsol,viz[100001];
void DF(int i)
{
    viz[i]=1;
    while(v[i])
            {
              if(!viz[v[i]->info])
                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])
            {
                ++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);
    if(M==0)
    {
        fprintf(g,"%i",N);
        exit(0);
    }
    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;
        nod *x=(nod *)malloc(1*sizeof(nod));
        x->info=nr1;
        x->adr_urm=v[nr2];
        v[nr2]=x;
    }
    rez(N);
    fprintf(g,"%i",nrsol);
    return 0;
}