Pagini recente » Cod sursa (job #2380587) | Cod sursa (job #1411895) | Cod sursa (job #519128) | Cod sursa (job #535791) | Cod sursa (job #2388353)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct nod
{
int val;
nod *nnext;
};
struct nod *vecini[100005];
int v[100005], n, m;
struct nod *adauga(struct nod *h, int a)
{
struct nod *p = (struct nod *)malloc(sizeof(nod));
struct nod *cl;
p->val = a;
p->nnext = NULL;
if (h == NULL)
{
h = p;
return h;
}
else
{
cl = h;
while (cl->nnext != NULL)
{
cl = cl->nnext;
}
cl->nnext = p;
return h;
}
}
void dfs(int x)
{
struct nod *cp;
v[x] = 1;
if (vecini[x] != NULL)
{
cp = vecini[x];
while (cp != NULL)
{
if (!v[cp->val])
dfs(cp->val);
cp = cp->nnext;
}
}
// for (cp = vecini[x]; cp != NULL; cp = cp->nnext)
// if (!v[cp->val])
// dfs(cp->val);
}
int main()
{
int a, b, componenete = 0;
;
f >> n >> m;
for (int i = 1; i <= n; i++)
{
vecini[i] = NULL;
v[i] = 0;
}
for (int i = 1; i <= m; i++)
{
f >> a >> b;
vecini[a] = adauga(vecini[a], b);
vecini[b] = adauga(vecini[b], a);
}
f.close();
for (int i = 1; i <= n; i++)
{
if (!v[i])
{
dfs(i);
componenete++;
}
}
g << componenete;
g.close();
return 0;
}