Pagini recente » Cod sursa (job #2815747) | Borderou de evaluare (job #1576221) | Cod sursa (job #1080938) | miculstring | Cod sursa (job #2377546)
#include <bits/stdc++.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
class Nod {
private:
int id;
Nod *nxt;
public:
Nod() {
id = 0;
nxt = NULL;
}
Nod(int v) {
id = v;
nxt = NULL;
}
int getId() {
return id;
}
Nod *getNxt() {
return nxt;
}
void modifyNxt(Nod *nod) {
nxt = nod;
}
};
void push(Nod **x, int val) {
if (x == NULL) {
*x = new Nod(val);
return;
}
Nod *aux = new Nod(val);
aux -> modifyNxt(*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 -> getNxt())
if (!viz[son -> getId()])
dfs(son -> getId());
}
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;
}