Pagini recente » Cod sursa (job #3342175) | Cod sursa (job #2198172) | Cod sursa (job #2519735) | Cod sursa (job #3305725) | Cod sursa (job #3335001)
#include <fstream>
#include <vector>
#include <stack>
int main()
{
int n, m;
std::vector<std::vector<int>> la;
std::ifstream in("dfs.in");
in >> n >> m;
for (int i = 0; i < n; i ++) {
la.push_back(std::vector<int>());
}
for (int i = 0; i < m; i ++) {
int x, y;
in >> x >> y;
x --;
y --;
la[x].push_back(y);
la[y].push_back(x);
}
in.close();
std::vector<bool> este_parcurs(n, false);
int nr_comp_conexe = 0;
for (int i = 0; i < n; i ++) {
if (este_parcurs[i]) {
continue;
}
nr_comp_conexe ++;
std::stack<int> s;
s.push(i);
este_parcurs[i] = true;
while (!s.empty()) {
int act = s.top();
s.pop();
for (auto vec: la[act]) {
if (este_parcurs[vec]) {
continue;
}
este_parcurs[vec] = true;
s.push(vec);
}
}
}
std::ofstream out("dfs.out");
out << nr_comp_conexe;
out.close();
return 0;
}