Pagini recente » Cod sursa (job #2389018) | Monitorul de evaluare | Rating Boldi Sebastian (sebiix99) | Clasament cnrv_1 | Cod sursa (job #2325035)
#include<fstream.h>
ifstream f("dfs.in");
ofstream g("dfs.out");
#define Nmax 100100
long n, m, nr, viz[Nmax];
struct lista
{
long inf;
lista *urm;
}*a[Nmax];
void add(long x, long y)
{
lista * q = new lista;
q->inf = y;
q->urm = a[x];
a[x] = q;
}
void read()
{
long x, y;
f >> n >> m;
for(long i = 1; i <= m; i++)
{
f >> x >> y;
add(x, y);
add(y, x);
}
}
void alg(int x)
{
lista *c = new lista;
c->inf = x;
c->urm = NULL;
lista *u = c;
while(c)
{
for(lista *q = a[c->inf]; q; q = q->urm)
{
if(viz[q->inf] == 0)
{
lista *p = new lista;
p->inf = q->inf;
p->urm = NULL;
u->urm = p;
u = p;
viz[q->inf] = 1;
}
}
c = c->urm;
}
}
int main()
{
read();
for(long i = 1; i <= n; i++)
if(viz[i] == 0)
{
alg(i);
nr++;
}
g << nr << endl;
f.close();
g.close();
return 0;
}