Pagini recente » Cod sursa (job #3294824) | Cod sursa (job #2519382) | Runda 4, preONI 2006 | Cod sursa (job #3287759) | Cod sursa (job #2645671)
#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int NMAX = 100505;
int N, M, components;
vector<int> G[NMAX];
stack<int> currPath;
bool visited[NMAX];
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> N >> M;
int x, y;
for (int edge = 0; edge < M; edge++) {
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int node = 1; node <= N; node++) {
if (!visited[node]) {
components++;
currPath.push(node);
visited[node] = true;
while (!currPath.empty()) {
int topNode = currPath.top();
if (!G[topNode].empty()) {
int nextNeighb = G[topNode].back();
G[topNode].pop_back();
if (!visited[nextNeighb]) {
visited[nextNeighb] = true;
currPath.push(nextNeighb);
}
} else {
currPath.pop();
}
}
}
}
cout << components << "\n";
return 0;
}