Cod sursa(job #2791764)

Utilizator lolotbogdanLolot Stefan-Bogdan lolotbogdan Data 30 octombrie 2021 23:57:39
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <map>
#include <list>
#include <unordered_map>

using namespace std;

ifstream f("dfs.in");
ofstream o("dfs.out");

class Graf {
	int noduri, muchii;
	unordered_map<int, list<int>>vecini;
	unordered_map<int, int> vizitat;

public:
	void citire();
	int get_noduri();
	int get_muchii();
	int get_vizitat(int nod);
	void adauga_muchie(int nod1, int nod2);
	//void sorteaza();
	void dfs(int varf);

};

void Graf::citire()
{
	f >> noduri >> muchii;
}

int Graf::get_noduri()
{
	return this -> noduri;
}

int Graf::get_muchii()
{
	return this -> muchii;
}

int Graf::get_vizitat(int nod)
{
	return vizitat[nod];
}

void Graf::adauga_muchie(int nod1, int nod2)
{
	vecini[nod1].push_back(nod2);
	vecini[nod2].push_back(nod1);
}

//void Graf::sorteaza()
//{
//	for (int i = 1; i <= noduri; i++)
//		vecini[i].sort();
//}

void Graf::dfs(int varf)
{
	//cout << varf << " ";
	vizitat[varf] = 1;

	for (auto i = vecini[varf].begin(); i != vecini[varf].end(); i++)
		if (vizitat[*i] != 1)
			dfs(*i);
}

int main()
{
	Graf g;
	g.citire();

	int noduri = g.get_noduri(), muchii = g.get_muchii();

	for (int i = 1; i <= muchii; i++)
	{
		int st, dr;
		f >> st >> dr;
		g.adauga_muchie(st, dr);
	}

	int sol = 0;

	//g.sorteaza();

	for (int i = 1; i <= noduri; i++)
		if (g.get_vizitat(i) != 1)
		{
			sol += 1;
			g.dfs(i);
		}

	 o << sol;
	return 0;
}