Pagini recente » Cod sursa (job #2715516) | Cod sursa (job #1130301) | Cod sursa (job #1143606) | Cod sursa (job #3032114) | Cod sursa (job #2434717)
#include <fstream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
string const inFile("dfs.in");
string const outFile("dfs.out");
ifstream _read(inFile);
ofstream _write(outFile);
void Read(unsigned &n, unsigned &m, vector<vector<unsigned>> &nodes) {
_read >> n;
_read >> m;
nodes.resize(n);
unsigned node1;
unsigned node2;
for (unsigned i = 0; i < m; ++i) {
_read >> node1;
_read >> node2;
nodes[node1 - 1].push_back(node2 - 1);
nodes[node2 - 1].push_back(node1 - 1);
}
}
void DFS(vector<vector<unsigned>> const &nodes, vector<bool> &vis, unsigned const start) {
stack<unsigned> _stack;
unsigned node;
bool found;
_stack.push(start);
while (_stack.empty() == false) {
node = _stack.top();
vis[node] = true;
found = false;
for (unsigned i = 0; i < nodes[node].size(); ++i) {
if (vis[nodes[node][i]] == true) {
continue;
}
_stack.push(nodes[node][i]);
found = true;
break;
}
if (found == false) {
_stack.pop();
}
}
}
unsigned Count(vector<vector<unsigned>> &nodes) {
unsigned _count = 0;
vector<bool> vis(nodes.size(), false);
for (unsigned i = 0; i < nodes.size(); ++i) {
if (vis[i] == false) {
DFS(nodes, vis, i);
++_count;
}
}
return _count;
}
int main() {
unsigned n;
unsigned m;
vector<vector<unsigned>> nodes;
Read(n, m, nodes);
_write << Count(nodes);
return 0;
}