Cod sursa(job #3249197)

Utilizator AndroidusAlex Turculet Androidus Data 15 octombrie 2024 13:24:00
Problema Parcurgere DFS - componente conexe Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void parc(int nod, const vector<vector<int>>& lista, vector<int>& conex, int compConexe)
{
	conex[nod] = compConexe;

	for (int i = 0; i < lista[nod].size(); ++i)
	{
		if (conex[lista[nod][i]] == -1)
			parc(lista[nod][i], lista, conex, compConexe);
	}
}

int main()
{
	int n, m, compConexe = 0;

	ifstream fin("dfs.in");
	fin >> n >> m;

	vector<int> conex(n, -1);
	vector<vector<int>> lista(n);

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

	fin.close();

	for (int i = 0; i < n; ++i)
	{
		if (conex[i] == -1)
		{
			parc(i, lista, conex, compConexe);
			compConexe++;
		}
	}

	ofstream fout("dfs.out");
	fout << compConexe << endl;
	fout.close();

	return 0;
}