Cod sursa(job #369187)

Utilizator loginLogin Iustin Anca login Data 27 noiembrie 2009 15:06:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 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 dfs (int k, int nrc)
{
	nod *p;
	p=a[k];
	v[k]=nrc;
	while (p)
	{	
		if (v[p->info]==0)
		{
			v[p->info]=nrc;
		    dfs(p->info, nrc);
		}
		p=p->next;
	}
}
	
int main ()
{
	citire ();
	for (int i=1;i<=n;i++)
		if (v[i]==0)
			dfs(i, ++nrc);
	fout<<nrc;
	return 0;
}