Cod sursa(job #369214)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 27 noiembrie 2009 15:50:19
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<iostream>
using namespace std;
#define max 100001
struct nod{
		int info;
		nod* next;
	};
int n,v[max],nrc;
nod *a[max];
void read()
{
	int m,i,j;
	ifstream fin("dfs.in");
	fin>>n>>m;
	for(int i=1;i<=n;i++)
		a[i]=NULL;
	for(;m;--m)
	{
		fin>>i>>j;
		nod *t=new nod;
		t->info=j;
		t->next=a[i];
		a[i]=t;
		t=new nod;
		t->info=i;
		t->next=a[j];
		a[j]=t;
	}
	fin.close();
}
void dfs(int i)
{
	v[i]=1;
	nod *t;
	for(t=a[i];t;t=t->next)
		if(v[t->info]==0)
		{
			//t[k]=i;
			dfs(t->info);
		}
}
void bfs (int l, int nrc)
{
    int k;
    nod *st, *dr;
    st=dr=new nod;
    st->info=l;
    st->next=NULL;
    v[l]=nrc;
    while (st)
    {
        k=st->info;
        nod *p;
        p=a[k];
        while (p)
        {
            if (v[p->info]==0)
            {
                v[p->info]=nrc;
                nod *q=new nod;
                q->info=p->info;
                q->next=NULL;
                dr->next=q;
                dr=q;
            }
            p=p->next;
        }
        p=st;
        st=st->next;
        delete p;
    }
}
int main()
{
	read();
	int nrc=0;
	for(int i=1;i<=n;i++)
		if(v[i]==0)
			bfs(i),nrc++;
	FILE *fout=fopen("dfs.out","w");
	fprintf(fout,"%d",nrc);
	return 0;
}