Pagini recente » Cod sursa (job #567712) | Cod sursa (job #1407123) | Cod sursa (job #2531593) | Cod sursa (job #43496) | Cod sursa (job #2789911)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
class Graf {
vector<list<int>> noduri;
void dfs(int nod, vector<bool> &vizitate) {
vizitate[nod] = true;
for(auto i: noduri[nod])
if(!vizitate[i])
dfs(i, vizitate);
}
public:
Graf(vector<list<int>> _noduri) : noduri(_noduri) {}
friend ostream& operator<< (ostream& os, Graf graf) {
os << graf.noduri.size() << " nodes\n";
for(int i = 0; i < graf.noduri.size(); i++) {
os << "node " << i << ": ";
for(int j: graf.noduri[i])
os << j << " ";
os << "\n";
}
return os;
}
int nrConexe() {
vector<bool> vizitate(noduri.size());
int nr = 0;
for(int i = 0; i < noduri.size(); i++)
if(!vizitate[i]) {
nr++;
dfs(i, vizitate);
}
return nr;
}
};
int main() {
ifstream in("file");
ofstream out("dfs.out");
int noduri, muchii;
in >> noduri >> muchii;
vector<list<int>> aux(noduri);
for(int i = 0; i < muchii; i++) {
int x1, x2;
in >> x1 >> x2;
aux[x1 - 1].push_back(x2 - 1);
aux[x2 - 1].push_back(x1 - 1); // daca e neorientat
}
Graf graf(aux);
out << graf.nrConexe();
return 0;
}