Pagini recente » Cod sursa (job #1880923) | Cod sursa (job #1269922) | Cod sursa (job #464706) | Cod sursa (job #612707) | Cod sursa (job #2325382)
#include<fstream>
using namespace std;
#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(istream& f)
{
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()
{
ifstream f;
f.open("dfs.in");
ofstream g;
g.open("dfs.out");
read(f);
for(long i = 1; i <= n; i++)
if(viz[i] == 0)
{
alg(i);
nr++;
}
g << nr << endl;
f.close();
g.close();
return 0;
}