Pagini recente » Cod sursa (job #11224) | Cod sursa (job #1834913) | Cod sursa (job #2589928) | Cod sursa (job #637828) | Cod sursa (job #1438050)
#include <iostream>
#include <fstream>
#include <vector>
class Graf
{
private:
std::vector< std::vector<int> > adiacenta;
int n, m;
std::vector<bool> vizit;
public:
Graf();
Graf(int n, int m);
int get_n(){ return n; }
int get_m(){ return m; }
bool vizitat(int i);
void citire();
void afisare();
void DFS_conexe(int nod);
};
Graf::Graf()
{
}
Graf::Graf(int n, int m)
{
this->adiacenta.resize(n + 1);
this->vizit.resize(n + 1, false);
this->n = n;
this->m = m;
}
bool Graf::vizitat(int i)
{
if (this->vizit[i] == true)
{
return true;
}
else
{
return false;
}
}
void Graf::citire()
{
int x, y;
std::ifstream f("dfs.in");
f >> x >> y;
for (int i = 0; i <= this->get_m(); i++)
{
f >> x >> y;
this->adiacenta[x].push_back(y);
}
}
void Graf::afisare()
{
std::ofstream g("dfs.out");
for (int i = 1; i <= this->get_n(); i++)
{
for (int j = 1; j < this->adiacenta[i].size(); j++)
{
g << i << " " << this->adiacenta[i][j] << "\n";
}
}
}
void Graf::DFS_conexe(int nod)
{
this->vizit[nod] = true;
int aux;
for (int i = 0; i < this->adiacenta[nod].size(); i++)
{
aux = this->adiacenta[nod][i];
if (this->vizit[aux] == false)
{
DFS_conexe(aux);
}
}
}
int n, m;
int main()
{
std::ifstream f("dfs.in");
std::ofstream g("dfs.out");
f >> n >> m;
Graf graf(n, m);
graf.citire();
int contor = 0;
for (int i = 1; i <= n; i++)
{
if (graf.vizitat(i) == false)
{
contor++;
graf.DFS_conexe(i);
}
}
g << contor;
return 0;
}