Pagini recente » Clasament simulareinfo1_3 | Cod sursa (job #1736417) | Profil raressarb | Cod sursa (job #3138052) | Cod sursa (job #1800764)
//
// Created by marius on 11/8/16.
//
#include <fstream>
#include <vector>
#include <map>
#include <cstring>
using namespace std;
class Edge
{
private:
int first;
private:
int second;
public:
Edge() {}
Edge(int first, int second) : first(first), second(second) {}
int getFirst() const {
return first;
}
int getSecond() const {
return second;
}
Edge& setFirst(int first) {
this->first = first;
return *this;
}
Edge& setSecond(int second) {
this->second = second;
return *this;
}
friend std::istream& operator>> (std::istream &in, Edge & edge)
{
in >> edge.first;
in >> edge.second;
return in;
}
};
class Graph
{
private:
int numberOfVertices;
map<int, vector<int>> nodes;
void dfs(int start, bool marked[])
{
marked[start] = true;
if (this->nodes.find(start) == this->nodes.end()) {
return;
}
for(auto node : this->nodes.find(start)->second) {
if (!marked[node]) {
this->dfs(node, marked);
}
}
}
public:
Graph(int numberOfVertices) : numberOfVertices(numberOfVertices) {}
void addEdge(const Edge & edge) {
if (this->nodes.find(edge.getFirst()) == this->nodes.end()) {
this->nodes.insert(make_pair(edge.getFirst(), vector<int>()));
}
if (this->nodes.find(edge.getSecond()) == this->nodes.end()) {
this->nodes.insert(make_pair(edge.getSecond(), vector<int>()));
}
this->nodes.find(edge.getFirst())->second.push_back(edge.getSecond());
this->nodes.find(edge.getSecond())->second.push_back(edge.getFirst());
}
int getNrComponenteConexe() {
bool marked[this->numberOfVertices];
memset(marked, 0, sizeof(marked));
int cnt = 0;
for(int i = 1; i <= this->numberOfVertices; i++) {
if (!marked[i]) {
this->dfs(i, marked);
cnt++;
}
}
return cnt;
}
};
int main() {
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m;
in >> n >> m;
Graph graph(n);
Edge edge;
for(; m; m--) {
in >> edge;
graph.addEdge(edge);
}
out << graph.getNrComponenteConexe();
in.close();
out.close();
return 0;
}