Pagini recente » Cod sursa (job #774517) | Cod sursa (job #300844) | Cod sursa (job #1710433) | Cod sursa (job #128617) | Cod sursa (job #2791746)
#include <iostream>
#include <fstream>
#include <map>
#include <list>
using namespace std;
ifstream f("dfs.in");
ofstream o("dfs.out");
class Graf {
int noduri, muchii;
map<int, list<int>>vecini;
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;
}