Cod sursa(job #369221)

Utilizator dead_knightTitei Paul Adrian dead_knight Data 27 noiembrie 2009 16:11:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 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;
        p=new nod;
        p->info=i;
        p->next=a[j];
        a[j]=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;
    }
}

void bfs(int s, int nrc)
{
	int k;
	nod *st,*dr;
	st=dr=new nod;
	dr->info=s;
	dr->next=NULL;
	v[s]=nrc;
	while(st)
	{
		k=st->info;
		for(nod *p=a[k];p;p=p->next)
		    if(v[p->info]==0)
			   {
				   nod *q=new nod;
				   q->info=p->info;
				   q->next=NULL;
				   dr->next=q;
				   dr=q;
				   v[p->info]=nrc;
				 }
	 nod *t=st;
	 st=st->next;
	 delete t;
   }
}


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