Pagini recente » Monitorul de evaluare | Cod sursa (job #1594808) | Cod sursa (job #1266671) | Cod sursa (job #896607) | Cod sursa (job #2424465)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
class graph {
int vertices;
int edges;
vector<list<int>> adjacency;
vector<bool> visited;
friend istream& operator>>(istream& in, graph& g) {
int r1, r2;
in >> g.vertices >> g.edges;
for (int i = 0; i <= g.vertices; i++) {
list<int> *insertMe = new list<int>;
g.adjacency.push_back(*insertMe);
g.visited.push_back(false);
}
for (int i = 0; i < g.edges; i++) {
in >> r1 >> r2;
g.adjacency[r1].push_back(r2);
}
return in;
}
public:
void dfs(int orig) {
int popped;
vector<int> stack;
stack.push_back(orig);
while (!stack.empty()) {
popped = stack.front();
stack.erase(stack.begin());
if (!visited[popped]) {
visited[popped] = true;
for (auto neighbour : adjacency[popped]) {
stack.push_back(neighbour);
}
}
}
}
int components() {
int count = 0;
for (int i = 0; i < vertices; i++) {
if (!visited[i]) {
dfs(i);
count++;
}
}
return count;
}
};
int main() {
graph G;
ifstream in("dfs.in");
in >> G;
in.close();
ofstream out("dfs.out");
out << G.components();
out.close();
return 0;
}