Pagini recente » Cod sursa (job #407716) | Cod sursa (job #1669048) | Cod sursa (job #2222486) | Cod sursa (job #1991843) | Cod sursa (job #153046)
Cod sursa(job #153046)
#include <iostream>
#include <string>
#define NMAX 100000+10
#define MMAX 200000+10
#define Dim (1<<13)
using namespace std;
long n, m, vec[MMAX], poz[NMAX], comp[NMAX], nr, Poz;
char lin[Dim];
inline void cit(unsigned &x){
x=0;
while (lin[Poz]<'0' || lin[Poz]>'9'){
Poz++;
if (Poz == Dim) fread(lin, 1, Dim, stdin), Poz=0;
}
while (lin[Poz]>='0' && lin[Poz]<='9'){
x = 10*x+lin[Poz++]-'0';
if (Poz == Dim) fread(lin, 1, Dim, stdin), Poz=0;
}
}
inline 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);
cit(n); cit(m);
a = (long *) malloc ( m * sizeof(long) );
b = (long *) malloc ( m * sizeof(long) );
for (i = 1; i <= m; ++i)
{
cit(a[i]); cit(b[i]);
poz[a[i]]++;
poz[b[i]]++;
}
for (i = 1; i <= n+1; ++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 = 0;
while (k < n)
{
k++;
if (!comp[k])
nr++, df(k);
}
printf("%ld", nr);
return 0;
}