Pagini recente » Cod sursa (job #958622) | Cod sursa (job #380623) | Cod sursa (job #2930321) | Cod sursa (job #511638) | Cod sursa (job #2645669)
#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int NMAX = 100505;
struct pathEntry {
int node, nextIdx;
};
int N, M, components;
vector<int> G[NMAX];
stack<pathEntry> 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, 0});
visited[node] = true;
while (!currPath.empty()) {
pathEntry topEntry = currPath.top();
currPath.pop();
if (topEntry.nextIdx != G[topEntry.node].size()) {
currPath.push({topEntry.node, topEntry.nextIdx + 1});
int nextNeighb = G[topEntry.node][topEntry.nextIdx];
if (!visited[nextNeighb]) {
visited[nextNeighb] = true;
currPath.push({nextNeighb, 0});
}
}
}
}
}
cout << components << "\n";
return 0;
}