Pagini recente » Cod sursa (job #3316874) | Cod sursa (job #3316828) | Cod sursa (job #3328815) | Cod sursa (job #3316864) | Cod sursa (job #3314748)
#include <iostream>
#include <cstdio>
namespace InParser
{
static constexpr int BSIZE = (1 << 16);
static int pos = (BSIZE - 1);
static char buff[BSIZE];
char get_char()
{
++pos;
if (pos == BSIZE)
{
pos = 0;
int n = fread(buff, 1, BSIZE, stdin);
if (n != BSIZE)
for (int i = n; i < BSIZE; ++i)
buff[i] = 0;
}
return buff[pos];
}
unsigned int get_unsigned_int()
{
unsigned int answer = 0;
for (;;)
{
char ch = get_char();
if ((ch >= '0') && (ch <= '9'))
{
answer = (unsigned int)(ch - '0');
break;
}
}
for (;;)
{
char ch = get_char();
if ((ch >= '0') && (ch <= '9'))
answer = (answer * 10) + (unsigned int)(ch - '0');
else
break;
}
return answer;
}
};
void dfs(unsigned int *N, unsigned int *F, bool *used, const int node = 1)
{
used[node] = true;
for (unsigned int i = N[node]; i < N[(node + 1)]; ++i)
if (!used[F[i]])
dfs(N, F, used, F[i]);
return;
}
int main()
{
std ::ios_base ::sync_with_stdio(false);
std ::cin.tie(nullptr);
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
unsigned int n = InParser ::get_unsigned_int(), m = InParser ::get_unsigned_int();
unsigned int *N = (unsigned int *)calloc((n + 2), sizeof(unsigned int));
unsigned int *F = (unsigned int *)malloc((m << 1) * sizeof(unsigned int));
std ::pair<int, int> *edges = (std ::pair<int, int> *)malloc(m * sizeof(std ::pair<int, int>));
for (unsigned int i = 0; i < m; ++i)
{
unsigned int x = InParser ::get_unsigned_int(),
y = InParser ::get_unsigned_int();
++N[x], ++N[y];
edges[i] = {x, y};
}
for (unsigned int i = 2; i <= (n + 1); ++i)
N[i] += N[(i - 1)];
for (unsigned int i = 0; i < m; ++i)
{
unsigned int x = edges[i].first, y = edges[i].second;
F[--N[x]] = y, F[--N[y]] = x;
}
bool *used = (bool *)calloc((n + 1), sizeof(bool));
unsigned int answer = 0;
for (unsigned int node = 1; node <= n; ++node)
if (!used[node])
++answer,
dfs(N, F, used, node);
printf("%d\n", answer);
if (N)
free(N);
if (F)
free(F);
if (edges)
free(edges);
if (used)
free(used);
return 0;
}