Pagini recente » Cod sursa (job #1862290) | Cod sursa (job #2678431) | Cod sursa (job #1629339) | Cod sursa (job #1786728) | Cod sursa (job #2194400)
#include <iostream>
#include <fstream>
#define MAX_N 100001
#define MAX_M 200001
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, nr, vf[2 * MAX_M], urm[2 * MAX_M], lst[MAX_N], viz[MAX_N];
void adauga(int x, int y)
{
nr++;
vf[nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
}
void dfs(int x)
{
viz[x] = true;
int p = lst[x], y;
while (p != 0) {
y = vf[p];
if (!viz[y]) dfs(y);
p = urm[p];
}
}
int main()
{
int x, y, c;
fin >> n >> m;
for (int i = 1 ; i <= m ; i++) {
fin >> x >> y;
adauga(x, y);
adauga(y, x);
}
c = 0;
for (int i = 1 ; i <= n ; i++) if (!viz[i]) c++, dfs(i);
fout << c;
return 0;
}