Cod sursa(job #632933)

Utilizator JohannesJohannes Dragulanescu Johannes Data 12 noiembrie 2011 15:47:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#define n_max 100001

#include <vector>
#include <stdio.h>

using namespace std;

int n,m;
vector <int> a[n_max];
int sel[n_max];

void dfs(int nod_sursa)
{ 
	sel[nod_sursa]=1;
	
	for( int i=0; i<a[nod_sursa].size(); i++)
		// se parcurg vecinii nodului sursa. daca sunt neselectati devin, pe rand, noduri sursa la randul lor.
		if (sel[a[nod_sursa][i]] == 0)
			dfs(a[nod_sursa][i]);
}

int main()
{
	int x,y;
	int componente_conexe=0;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	scanf("%d %d", &n,&m);

	for(int i=1; i<=m; i++)
	{ 
		scanf("%d %d",&x,&y);

		a[x].push_back(y);
		a[y].push_back(x);

		// se retin nodurile grafului neorientat dar pentru fiecare nod se retin si vecinii lui
	}

	for (int nod_sursa=1; nod_sursa<=n; nod_sursa++)
	{
		// se parcurg nodurile si se verifica daca sunt deja selectate
		if (sel[nod_sursa] == 0)
		{ 
			componente_conexe++; 
			dfs(nod_sursa);
		}
	}
	printf("%d",componente_conexe);

	return 0;
}