Pagini recente » Cod sursa (job #2341550) | Cod sursa (job #2978326) | Cod sursa (job #1870277) | Cod sursa (job #1825422) | Cod sursa (job #2479756)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
const int N = 100001;
bool viz[N];
int vf[N], lst[N], urm[N];
int nr, n, m;
void dfs(int x) {
viz[x] = true;
int y;
for (int p = lst[x]; p != 0; p = urm[p]) {
y = vf[p];
if (!viz[y]) {
dfs(y);
}
}
}
void adauga(int x, int y) {
vf[++nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
}
struct comp {
int x, y;
}v[N];
int main() {
in >> n >> m;
int cnt = 0;
for (int i = 1; i <= m; i++) {
in >> v[i].x >> v[i].y;
adauga(v[i].x, v[i].y);
adauga(v[i].y, v[i].x);
}
for (int i = 1; i <= n; i++) {
if (viz[i] == false) {
dfs(i);
cnt++;
}
}
out << cnt;
return 0;
}