Pagini recente » Cod sursa (job #891527) | Cod sursa (job #3276000) | Cod sursa (job #760224) | Cod sursa (job #2248721) | Cod sursa (job #2789902)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
class Graf {
vector<list<int>> noduri;
void dfs(int nod, vector<bool> &viziate) {
viziate[nod] = true;
for(auto i: noduri[nod])
if(!viziate[i])
dfs(i, viziate);
}
public:
Graf(vector<list<int>> _noduri, bool _oriented=true) : 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> viziate(noduri.size());
int nr=0;
for(int i = 0; i < noduri.size(); i++) {
if(!viziate[i]) {
dfs(i, viziate);
nr++;
}
}
return nr;
}
};
int main() {
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m;
in >> n >> m;
vector<list<int>> aux(n);
for(int i = 0; i < m; i++) {
int x1, x2;
in >> x1 >> x2;
aux[x1].push_back(x2);
aux[x2].push_back(x1); // daca e neorientat
}
Graf graf(aux);
out << graf.nrConexe();
return 0;
}