Cod sursa(job #2377909)

Utilizator chioseChiose Razvan-Alexandru chiose Data 11 martie 2019 13:51:00
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>

void dfs(int node, std::vector<int> graf[], int* viz)
{
	viz[node] = 1;
	int lim = graf[node].size();
	int vecin;
	for (int i = 0; i < lim; i++)
	{
		vecin = graf[node][i];
		if (viz[vecin] == 0)
			dfs(vecin, graf, viz);
	}
}

int main()
{
	std::vector <int> graf[100000];
	std::ifstream in("dfs.in");
	std::ofstream out("dfs.out");

	int m, n, x, y;
	in >> n >> m;
	int* viz = new int[n+1];

	for (int i = 0; i <= n; i++)
		viz[i] = 0;

	for (int i = 0; i < m; i++)
	{
		in >> x >> y;
		graf[x].push_back(y);
		graf[y].push_back(x);
	}

	int nr = 0;
	for(int i=1;i<=n;i++)
		if (viz[i] == 0)
		{
			nr++;
			dfs(i, graf, viz);
		}

	out << nr;

	in.close();
	out.close();

	return 0;
}