Pagini recente » Cod sursa (job #2506719) | Cod sursa (job #319102) | Cod sursa (job #3030034) | Cod sursa (job #747419) | Cod sursa (job #2424472)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
class graph {
int vertices;
int edges;
vector<vector<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++) {
vector<int>* insertMe = new vector<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);
g.adjacency[r2].push_back(r1);
}
return in;
}
public:
void dfs(int orig) {
visited[orig] = true;
for (auto neighbour : adjacency[orig]) {
if (!visited[neighbour])
dfs(neighbour);
}
}
int components() {
int count = 0;
for (int i = 1; i <= vertices; i++) {
if (!visited[i]) {
dfs(i);
visited[i] = true;
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;
}