Pagini recente » Cod sursa (job #2687316) | Cod sursa (job #2364868) | Cod sursa (job #361763) | Cod sursa (job #858046) | Cod sursa (job #2276614)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100005;
vector<int> g[NMAX];
bool d[NMAX];
void dfs(int root) {
stack<int> s;
s.push(root);
d[root] = true;
while (!s.empty()) {
int node = s.top();
s.pop();
for (int v : g[node]) {
if (!d[v]) {
s.push(v);
d[v] = true;
}
}
}
}
int main() {
ifstream iff("dfs.in");
ofstream off("dfs.out");
int N, M;
iff >> N >> M;
for (int i = 0; i <= N; ++i) {
d[i] = false;
}
for (int i = 0; i < M; ++i) {
int n1, n2;
iff >> n1 >> n2;
g[n1].push_back(n2);
g[n2].push_back(n1);
}
int count = 0;
for (int i = 1; i <= N; ++i) {
if (!d[i]) {
dfs(i);
count += 1;
}
}
off << count;
return 0;
}