Cod sursa(job #369212)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 27 noiembrie 2009 15:42:05
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<fstream>
#include<cstdlib>
#define MAX 100000
using namespace std;
struct nod{int info;
        nod *next;};
int n,m,v[100001];
nod * a[100001];
FILE *fout=fopen("dfs.out", "w");

void write()
{
    fprintf(fout,"%d %d\n", n, m);
    for(int i=1;i<=n;i++)
    {
        nod * p = a[i];
        fprintf(fout,"%d : ",i);
        while(p)
        {
            fprintf(fout,"%d ", p->info);
            p=p->next;
        }
        fprintf(fout,"\n");
    }

}

void read()
{
    FILE *fin=fopen("dfs.in", "r");
    fscanf(fin,"%d %d",& n,& m);
    for(int i=1;i<=n;i++)
        a[i]=NULL;
    while(m)
    {
        int i,j;
        fscanf( fin ,"%d %d",& i,& j);
        nod *p=new nod;
        p->info=j;
        p->next=a[i];
        a[i]=p;
        m--;
    }

}

void dfs(int varf, int nrc)
{
    v[varf]=nrc;
    nod *p = a[varf];
    while(p)
    {
        if(v[p->info]==0)
        {
            dfs(p->info,nrc);
        }
        p=p->next;
    }
}

void sterge(nod *p)
{
    nod *t=p;
    while(p)
    {
        t=p;
        p=p->next;
        delete t;
    }
}


int main()
{
    read();
    //write();
    int nrc=0;
    for(int i=1;i<=n;i++)
        if(v[i]==0)
            dfs(i,++nrc);
    fprintf( fout ,"%d" , nrc );
    for(int i=1;i<=n;i++)
        sterge(a[i]);
    return 0;
}