Cod sursa(job #1607399)

Utilizator krityxAdrian Buzea krityx Data 21 februarie 2016 02:33:15
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>

using namespace std;

void dfs(int nod, vector<vector<int>> G, vector<bool> &seen)
{
	seen[nod] = true;
	for (vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); it++)
	{
		if (!seen[*it])
		{
			dfs(*it, G, seen);
		}
	}
}

int main()
{
	vector<vector<int>> G;
	vector<bool> seen;
	int N, M, i, j, x, y;
	ifstream f("dfs.in");
	f >> N >> M;
	G.resize(N + 1);
	seen.resize(N + 1, 0);
	for (i = 1; i <= M; i++)
	{
		f >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	int num = 0;
	for (int i = 1; i <= N; i++)
	{
		if (!seen[i])
		{
			dfs(i, G, seen);
			num++;
		}
	}

	ofstream g("dfs.out");
	g << num;
	g.close();

	return 0;
}