Pagini recente » Cod sursa (job #2403258) | Cod sursa (job #482678) | Cod sursa (job #1859695) | Cod sursa (job #1195086) | Cod sursa (job #2692929)
#include <iostream>
#include <vector>
#include <list>
using namespace std;
struct Nod {
bool vizitat = false;
vector <int> from;
};
int main() {
//freopen("FileIn.txt", "r", stdin);
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int n, m, x, y, i = 1, total = 0;
scanf("%d %d", &n, &m);
vector <Nod> nodes(n + 1);
list <int> order;
while (m--) {
scanf("%d %d", &x, &y);
nodes[x].from.push_back(y);
nodes[y].from.push_back(x);
}
while (i <= n) {
order.push_back(i);
nodes[i].vizitat = true;
while (!order.empty()) {
vector <int> act = nodes[order.front()].from;
while (!act.empty()) {
if (!nodes[act.back()].vizitat)
order.push_back(act.back());
nodes[act.back()].vizitat = true;
act.pop_back();
}
order.pop_front();
}
while (i <= n && nodes[i].vizitat)
i++;
total++;
}
printf("%d", total);
return 0;
}