Pagini recente » Cod sursa (job #1733576) | Cod sursa (job #2793270) | Cod sursa (job #1978965) | Cod sursa (job #3267380) | Cod sursa (job #2629186)
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
int read () {
int ch;
while (!isdigit(ch=getchar()));
int ans=0;
do
ans = (ans<<3) + (ans<<1) + ch - '0';
while (isdigit(ch=getchar()));
return ans;
}
void print (int a) {
if (a) {
print(a/10);
putchar(a%10 + '0');
}
}
struct nod {
int inf;
struct nod *urm;
} **G;
void add (struct nod **p, int x) {
struct nod *e = (struct nod*) malloc(sizeof (struct nod));
e->inf=x;
e->urm=*p;
*p=e;
}
unsigned long long *bits;
void set (int i) {
bits[i>>6] |= (1ull << (i & 63));
}
int seen (int i) {
return (bits[i>>6] >> (i & 63)) & 1;
}
void dfs (int x) {
set(x);
for (struct nod *p=G[x]; p; p=p->urm)
if (!seen(p->inf))
dfs(p->inf);
}
int main (void) {
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int n, m;
n=read(), m=read();
bits = (unsigned long long*) calloc((n>>6) + 1, sizeof (unsigned long long));
G = (struct nod**) calloc(n+1, sizeof (struct nod*));
int i, j, ct=0;
for (; m; m--) {
i=read();
j=read();
add(G+i, j);
}
for (i=1; i<=n; ++i)
if (!seen(i)) {
++ct;
dfs(i);
}
print(ct);
return 0;
}