Cod sursa(job #369195)

Utilizator loginLogin Iustin Anca login Data 27 noiembrie 2009 15:22:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
# include <fstream>
using namespace std;
struct nod {
	int info;
	nod*next;};
int n, v[100003], nrc;
nod *a[100003];
ofstream fout ("dfs.out");

void citire ()
{
	int m;
	ifstream fin ("dfs.in");
	fin>>n>>m;
	for (int i=1;i<=n;i++)
		a[i]=NULL;
	for (;m;--m)
	{
		int i, j;
		fin>>i>>j;
		nod *t;
		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;
	}
}

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 ()
{
	citire ();
	for (int i=1;i<=n;i++)
		if (v[i]==0)
			bfs(i, ++nrc);
	fout<<nrc;
	return 0;
}