Cod sursa(job #330041)

Utilizator irene_mFMI Irina Iancu irene_m Data 8 iulie 2009 15:03:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream.h>
#define MaxN 100009
#define MaxM 200009

int s[MaxN],T[2][2*MaxM],n,m,uz[MaxN],nr;

void add(int x,int y,int &st)
{
	T[0][st]=y;
	T[1][st]=s[x];
	s[x]=st;
	st++;
}

void cit()
{
	int i,x,y,st=1;
	ifstream fin("dfs.in");
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		add(x,y,st);
		add(y,x,st);
	}
	fin.close();
}	

void DFS(int nod)
{
	uz[nod]=1;
	int p=s[nod];
	while(p)
	{
		if(!uz[T[0][p]])
			DFS(T[0][p]);
		p=T[1][p];
	}
}

void afis()
{
	ofstream fout("dfs.out");
	fout<<nr;
	fout.close();
}

int main()
{
	cit();
	for(int i=1;i<=n;i++)
		if(!uz[i])
		{
			nr++;
			DFS(i);
		}
	afis();
	return 0;
}