Pagini recente » Cod sursa (job #596115) | Cod sursa (job #1308863) | Cod sursa (job #792293) | Cod sursa (job #2362319) | Cod sursa (job #2368268)
#include <cstdio>
#include <vector>
#include <stack>
#define N_MAX 100001
int N, M, components = 0, component[N_MAX];
std::vector<int> graph[N_MAX];
std::stack<int> s;
void dfs(const int start, const int componentNumber) {
component[start] = componentNumber;
s.push(start);
// printf("%d -> %d\n", start, componentNumber);
while (!s.empty()) {
int current = s.top();
for (int it = 0; it < graph[current].size(); ++it) {
if (!component[graph[current][it]]) {
component[graph[current][it]] = componentNumber;
s.push(graph[current][it]);
// printf("%d -> %d\n", graph[current][it], componentNumber);
break;
}
}
if (current == s.top()) s.pop();
}
}
int main() {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d%d", &N, &M);
for (int it = 0; it < M; ++it) {
int x, y;
scanf("%d%d", &x, &y);
graph[--x].push_back(--y);
graph[y].push_back(x);
}
for (int it = 0; it < N; ++it) {
if (!component[it]) {
// printf("Starting for %d...", it);
dfs(it, ++components);
}
}
printf("%d\n", components);
return 0;
}