Cod sursa(job #1694638)

Utilizator andreilucaLuca Andrei andreiluca Data 25 aprilie 2016 18:36:44
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define NMAX 100000
#include <vector>
using namespace std;

int n,m;
vector<int> v[NMAX];
int etichete[NMAX];
FILE *in, *out;
void read();
void DFS(int,int);
int main()
{
	in = fopen("dfs.in","r");
	out = fopen("dfs.out","w");
	read();
	int k = 1;
	for (int i = 1; i <= n; i++)
	{
		if (etichete[i] == 0)
		{
			DFS(i, k);
			k++;
		}
	}
	fprintf(out, "%d", k-1);
	return 0;
}
void read()
{
	int x, y;
	fscanf(in,"%d%d",&n,&m);
	for (int i = 0; i < m; i++)
	{
		fscanf(in, "%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
}
void DFS(int nod, int eticheta)
{
	etichete[nod] = eticheta;
	for (int i = 0; i < v[nod].size();i++)
	if (etichete[v[nod][i]] == 0)
	{
		//etichete[v[nod][i]] = eticheta;
		DFS(v[nod][i],eticheta);
	}
}