Pagini recente » Cod sursa (job #1351783) | Cod sursa (job #3258315) | Cod sursa (job #777507) | Cod sursa (job #1512778) | Cod sursa (job #2664197)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("dfs.in");
ofstream out ("dfs.out");
int const nlim = 100001;
struct nod
{
int a;
nod * urm;
}*v[nlim];
void adaug( nod * & p, int x )
{
if ( p == NULL )
{
p = new nod;
p -> a = x;
p -> urm = NULL;
}
else
{
nod * q = p;
while(q -> urm != NULL)
q = q -> urm;
nod * f = new nod;
f -> a = x;
f -> urm = NULL;
q -> urm = f;
}
}
void dfs(int x, int viz[nlim])
{
viz[x] = 1;
while(v[x] != NULL)
{
if(viz[v[x]->a] == 0)
dfs(v[x] -> a, viz);
v[x] = v[x] -> urm;
}
}
int cont(int viz[nlim], int n)
{
int i, c = 0;
for ( i = 1; i <= n ;i ++ )
{
viz[i] = 0;
}
for( i = 1; i <= n; i ++ )
{
if ( viz[i] == 0 )
{
c ++ ;
dfs(i,viz);
}
}
return c;
}
int main()
{
int n, m, i, viz[nlim] = {0};
in >> n >> m;
for ( i = 1; i <= m ; i ++ )
{
int x, y;
in >> x >> y;
adaug(v[x],y);
adaug(v[y],x);
}
out << cont(viz,n);
return 0;
}