Pagini recente » Cod sursa (job #1111286) | Cod sursa (job #225110) | Cod sursa (job #1345650) | Cod sursa (job #378945) | Cod sursa (job #149527)
Cod sursa(job #149527)
#include <iostream>
#include <string>
#define NMAX 100000+10
#define MMAX NMAX*(NMAX+1)/2
using namespace std;
long n, m, vec[MMAX], poz[NMAX], comp[NMAX], nr;
void df(long x)
{
long i;
comp[x] = nr;
for ( i = poz[x]+1; i <= poz[x+1]; ++i)
if (!comp[vec[i]])
df(vec[i]);
}
int main(void)
{
long i, *a, *b, k;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%ld %ld", &n, &m);
a = (long *) malloc ( m * sizeof(long) );
b = (long *) malloc ( m * sizeof(long) );
for (i = 1; i <= m; ++i)
{
scanf("%ld %ld", a+i, b+i);
poz[a[i]]++;
poz[b[i]]++;
}
for (i = 1; i <= n; ++i)
poz[i] += poz[i-1];
for (i = 1; i <= m; ++i)
{
vec[ poz[a[i]] ] = b[i];
vec[ poz[b[i]] ] = a[i];
poz[a[i]]--;
poz[b[i]]--;
}
free(a), free(b);
nr = 0, k = 1;
while (k <= n)
{
if (!comp[k])
nr++, df(k);
k++;
}
printf("%ld", nr);
return 0;
}