Cod sursa(job #585475)

Utilizator varuvasiTofan Vasile varuvasi Data 29 aprilie 2011 18:11:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
//#include "stdafx.h"

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

using namespace std;

#define maxn 100333

int n, m;
vector<int> v[maxn];
int viz[maxn];

void dfs(int nod)
{
	int i;
	for (i=0; i<v[nod].size(); i++)
		if (!viz[v[nod][i]])
		{
			viz[v[nod][i]] = 1;
			dfs(v[nod][i]);
		}
}

int main()
{
	int i, j, x, y, comp_conexe = 0;
	FILE *fin = fopen("dfs.in", "rt"), *fout = fopen("dfs.out", "wt");

	fscanf(fin, "%d %d", &n, &m);
	for (i=0; i<m; i++)
	{
		fscanf(fin, "%d %d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}

	for (i=1; i<=n; i++)
		if (!viz[i])
		{
			comp_conexe++;
			dfs(i);
		}

	fprintf(fout, "%d", comp_conexe);

	fclose(fin), fclose(fout);
	return 0;
}