Pagini recente » Cod sursa (job #2469298) | Cod sursa (job #2708576) | Cod sursa (job #1925780) | Cod sursa (job #1954758) | Cod sursa (job #2427319)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
using namespace std;
class Link {
private:
unsigned from;
unsigned to;
public:
Link(unsigned from, unsigned to): from(from), to(to) {}
unsigned getTo() {
return this->to;
}
};
class Graph {
private:
unsigned V;
std::list<Link> *adj;
void DFSUtil(unsigned start, bool *visited) {
std::stack<unsigned> s;
s.push(start);
while(!s.empty()) {
unsigned v = s.top();
s.pop();
if(!visited[v]) {
visited[v] = true;
for(auto it : adj[v])
s.push(it.getTo());
}
}
}
public:
Graph(unsigned V): V(V) {
adj = new std::list<Link>[V + 1];
}
void addEdge(unsigned from, unsigned to) {
Link first_link(from, to);
Link second_link(to, from);
adj[from].push_back(first_link);
adj[to].push_back(second_link);
}
void printGraph() {
for(unsigned i = 1; i <= this->V; i ++) {
for(auto it : adj[i]) {
std::cout << "nodul " << i << " este conectat cu " << it.getTo() << std::endl;
}
}
}
unsigned long connectedComponents() {
bool *visited = new bool[this->V + 1];
for(unsigned long i = 1; i <= this->V; i ++)
visited[i] = false;
unsigned long n = 0;
for (unsigned long i = 1; i <= this->V; i ++) {
if (!visited[i]) {
DFSUtil(i, visited);
n ++;
}
}
return n;
}
};
int main() {
std::ifstream in("dfs.in");
std::ofstream out("dfs.out");
unsigned long n, m, a, b;
in >> n >> m;
auto G = new Graph(n);
for (unsigned long i = 0; i < m; i ++) {
in >> a >> b;
G->addEdge(a, b);
}
out << G->connectedComponents();
return 0;
}