Pagini recente » Cod sursa (job #746743) | Cod sursa (job #1837310) | Cod sursa (job #2083889) | Cod sursa (job #162580) | Cod sursa (job #3272208)
#include <bits/stdc++.h>
using namespace std;
// ifstream in("citire.in");
ifstream in("dfs.in");
ofstream out("dfs.out");
const int infinity = numeric_limits<int>::max();
const int infinitytMin = numeric_limits<int>::min();
// muchie de la x la y cu costul cost
struct Muchie
{
int x, y;
int cost = 0;
int capacitate = -1;
int flux = -1;
Muchie() = default;
Muchie(int x, int y, int cost)
{
this->x = x;
this->y = y;
this->cost = cost;
}
Muchie(int x, int y)
{
this->x = x;
this->y = y;
}
Muchie(int x, int y, int flux, int capacitate)
{
this->x = x;
this->y = y;
this->flux = flux;
this->capacitate = capacitate;
}
};
bool comparison(Muchie m1, Muchie m2)
{
return m1.cost < m2.cost;
}
struct Nod
{
int nod;
int cost = 0;
int capacitate = -1;
int flux = -1;
Nod() = default;
Nod(int nod) { this->nod = nod; }
Nod(int nod, int cost)
{
this->nod = nod;
this->cost = cost;
}
Nod(int nod, int flux, int capacitate)
{
this->nod = nod;
this->flux = flux;
this->capacitate = capacitate;
}
bool operator<(const Nod &obj) const
{
return this->cost > obj.cost; //> pt min-heap
}
};
// vector<Muchie> dfsMuchii;
class Graf
{
public:
int nrNoduri;
int nrMuchii;
vector<bool> vizitat;
vector<int> grad_intern;
vector<int> grad_extern;
vector<vector<Nod>> lista_adiacenta;
vector<Muchie> muchii;
Graf() = default;
Graf(int nrNoduri)
{
this->nrNoduri = nrNoduri;
vizitat.resize(nrNoduri + 1);
grad_intern.resize(nrNoduri + 1, 0);
grad_extern.resize(nrNoduri + 1, 0);
lista_adiacenta.resize(nrNoduri + 1);
}
Graf(int nrNoduri, int nrMuchii)
{
this->nrMuchii = nrMuchii;
this->nrNoduri = nrNoduri;
vizitat.resize(nrNoduri + 1, false);
grad_intern.resize(nrNoduri + 1, 0);
grad_extern.resize(nrNoduri + 1, 0);
lista_adiacenta.resize(nrNoduri + 1);
}
void iterativeDFS(int start, vector<int> &tati)
{
int n = nrNoduri;
stack<int> stack;
stack.push(start);
while (!stack.empty())
{
int nod = stack.top();
stack.pop();
if (vizitat[nod] == false)
{
// cout << nod;
vizitat[nod] = true;
}
for (auto vecin : lista_adiacenta[nod])
if (vizitat[vecin.nod] == false)
{
// dfsMuchii.push_back(Muchie(nod, vecin.nod));
stack.push(vecin.nod);
}
// else if (tati[vecin.nod] != nod)
// return false;
}
// return true;
}
void printGraf()
{
for (int i = 1; i <= nrNoduri; i++)
{
cout << i << ": ";
for (auto nod : lista_adiacenta[i])
cout << nod.nod << "(" << nod.cost << ") ";
cout << endl;
}
}
};
int main()
{
int n, m;
in >> n >> m;
Graf g(n, m);
for (int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
g.lista_adiacenta[x].push_back(Nod(y));
g.lista_adiacenta[y].push_back(Nod(x));
}
vector<int> tata(n + 1);
int nr = 0;
for (int i = 1; i <= n; i++)
{
if (g.vizitat[i] == false)
{
nr++;
g.iterativeDFS(i, tata);
}
}
cout << nr;
return 0;
}