Cod sursa(job #3225576)

Utilizator teodora_lauraTeodora teodora_laura Data 18 aprilie 2024 00:02:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m;

void DFS(int nod, vector<bool>&vizitat, vector<vector<int>>&v)
{
	if (vizitat[nod])
		return;
	vizitat[nod] = true;
	for (int i = 0; i < v[nod].size(); i++)
		if (!vizitat[v[nod][i]])
			DFS(v[nod][i],vizitat,v);
}

int main()
{
	f >> n >> m;
	vector<vector<int>>v(n);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		f >> a >> b;
		a--; b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	vector<bool>vizitat(n,false);
	int nr = 0;
	for (int i = 0; i < n; i++)
	{
		if (!vizitat[i])
		{
			DFS(i, vizitat, v);
			nr++;
		}
	}
	g << nr;
}