Pagini recente » Cod sursa (job #33669) | Cod sursa (job #731800) | Cod sursa (job #560408) | Cod sursa (job #3294224) | Cod sursa (job #2377541)
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
struct Nod {
int id;
Nod *nxt;
Nod(int v) {
id = v;
nxt = NULL;
}
};
void push(Nod **x, int val) {
if (x == NULL) {
*x = new Nod(val);
return;
}
Nod *aux = new Nod(val);
aux -> nxt = *x;
*x = aux;
}
int n, m, cnt, x, y, viz[100100];
Nod *v[100100];
void dfs(int nod) {
viz[nod] = 1;
for (auto son = v[nod]; son != NULL; son = son -> nxt)
if (!viz[son -> id])
dfs(son -> id);
}
int main() {
in >> n >> m;
for (int i = 1; i <= m; i++) {
in >> x >> y;
push(&v[x], y);
push(&v[y], x);
}
for (int i = 1; i <= n; i++)
if (!viz[i]) {
cnt++;
dfs(i);
}
out << cnt;
return 0;
}