Pagini recente » Monitorul de evaluare | Autentificare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2379673)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
class Node {
private:
std::list<unsigned long> adj;
public:
std::list<unsigned long> getAdj() {
return adj;
}
void pushAdj(unsigned long a) {
adj.push_back(a);
}
};
class Graph {
private:
unsigned long noNodes;
Node *nodes;
public:
Graph(unsigned long noNodes): noNodes(noNodes) {
nodes = new Node[noNodes];
}
void push(unsigned long a, unsigned long b) {
nodes[a].pushAdj(b);
nodes[b].pushAdj(a);
}
void DFSUtil(unsigned long start, bool visited[]) {
std::stack<unsigned long> s;
s.push(start);
while(!s.empty()) {
auto node = s.top();
s.pop();
visited[node] = true;
for(auto it : nodes[node].getAdj()) {
if(!visited[it]) {
s.push(it);
}
}
}
}
unsigned long connectedComponents() {
bool *visited = new bool[this->noNodes];
for(unsigned long i = 0; i < this->noNodes; i++)
visited[i] = false;
unsigned long n = 0;
for (unsigned long i = 0; i < this->noNodes; 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->push(a, b);
}
out << G->connectedComponents();
return 0;
}