Pagini recente » Cod sursa (job #707754) | Cod sursa (job #2901177) | Cod sursa (job #1166303) | Cod sursa (job #401683) | Cod sursa (job #2761170)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
const int max_val = 100001;
struct nod
{
int info;
nod * urm;
}* lista[max_val];
int n, vizitat[max_val];
void adaugare (int x, int y)
{
nod * t = new nod;
t -> info = y;
t -> urm = lista[x];
lista[x] = t;
}
void dfs (int x)
{
vizitat[x] = 1;
nod * t = lista[x];
while (t)
{
if (vizitat[t -> info] == 0)
dfs(t -> info);
t = t -> urm;
}
}
int main()
{
int m;
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
adaugare (x, y);
adaugare (y, x);
}
int comp_conexe = 0;
for (int i = 1; i <= n; i++)
{
if (vizitat[i] == 0)
{
comp_conexe++;
dfs(i);
}
}
fout << comp_conexe;
return 0;
}