Pagini recente » Cod sursa (job #3316693) | Borderou de evaluare (job #2543325) | Borderou de evaluare (job #1466330) | Cod sursa (job #3314393) | Cod sursa (job #3314747)
#include <iostream>
#include <cstdio>
#include <vector>
using array_unsigned_int = std ::vector<unsigned int>;
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(array_unsigned_int &N, array_unsigned_int &F, std::vector<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();
array_unsigned_int N((n + 2), 0), F((m << 1));
std ::vector<std ::pair<int, int>> edges(m);
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;
}
std ::vector<bool> used((n + 1), false);
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);
return 0;
}