Pagini recente » Cod sursa (job #953009) | Cod sursa (job #2050650) | Cod sursa (job #1498019) | Cod sursa (job #2543740) | Cod sursa (job #2227888)
///by mihail stoian
#include <stdio.h>
#include <ctype.h>
#define Nadejde 100000
#define Dragoste 4096
int N, M;
int boss[Nadejde + 1];
int set[Nadejde / 32 + 1];
char buff[Dragoste];
int pos = Dragoste;
char getChar(FILE *f) {
if (pos == Dragoste) {
fread(buff, 1, Dragoste, f);
pos = 0;
}
return buff[pos++];
}
int freef(FILE *f) {
int result = 0;
char c;
do {
c = getChar(f);
} while (!isdigit(c));
do {
result = (result << 3) + (result << 1) + c - '0';
c = getChar(f);
} while (isdigit(c));
return result;
}
void init() {
int u;
for (u = 1; u <= Nadejde; u++) {
boss[u] = u;
}
}
int find(int u) {
int r = u, tmp;
while (r != boss[r]) {
r = boss[r];
}
while (u != boss[u]) {
tmp = boss[u];
boss[u] = r;
u = tmp;
}
return r;
}
void unify(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
boss[v] = u;
}
}
int getBit(int x) {
return (set[x >> 5] >> (x & 31)) & 1;
}
void setBit(int x) {
set[x >> 5] |= 1 << (x & 31);
}
int main(void) {
FILE *f = fopen("dfs.in", "r");
/* Initializarea datelor. */
init();
/* Citirea datelor. */
N = freef(f);
for (M = freef(f); M; M--) {
unify(freef(f), freef(f));
}
fclose(f);
/* Calcularea solutiei. */
int u, v, count = 0;
for (u = 1; u <= N; u++) {
v = find(u);
if (!getBit(v)) {
setBit(v);
count++;
}
}
/* Afisarea solutiei. */
freopen("dfs.out", "w", stdout);
fprintf(stdout, "%d\n", count);
fclose(stdout);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}