Cod sursa(job #1104734)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 10 februarie 2014 22:58:00
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>

using namespace std;

#define LE 1000

ifstream f("dfs.in");
ofstream g("dfs.out");

int lista_noduri[LE];
int muchii[LE][LE];
int inundat[LE];
int n,t,nr;

void BFS(int nod_start)
{
	nr=0;
	++nr;
	lista_noduri[nr]=nod_start;// bag nodul de start in lista de noduri proaspat inundate
	int j;
	
	for(j=1;j<=nr;++j)  /// forul asta e mai tricky umpic vezi restul algoritmului daca nu intalegi cum merge
	{
	   int Nod=lista_noduri[j]; /// asta este nodul proaspat inundat la care trebe sa i inund posibili vecini neinundati
	   
	   for(t=1;t<=n;++t)  ///parcurg toate nodurile
		  if (muchii[Nod][t]==1)/// daca am muchie de la nodul Nod la nodul t inseamnda ca t e vecin cu Nod
			if (inundat[t]==0) /// daca inundat[t] e 0 inseamna ca nu a fost inundat inainte , daca e 1 nu mai are rost sa il inund,pentru ca a fost inundat deja
			{
				inundat[t]=1;/// il marchez ca inundat
				++nr;
				lista_noduri[nr]=t; ///il bag in lista ca fiind un nod proaspat inundat
			}
	}
}

int main()
{
	int i,n1,n2,m;
	int nr_componente=0;
	
	f>>n>>m;// n=numar noduri, m=numar muchii
	for(i=1;i<=m;++i)///citesc muchiile
	{
		f>>n1>>n2;
		muchii[n1][n2]=1;
		muchii[n2][n1]=1;
	}
	
	for(i=1;i<=n;++i)
		if (inundat[i]==0) 
		{
			++nr_componente;
			BFS(i);
		}

	g<<nr_componente<<'\n';

	return 0;
}