Pagini recente » Cod sursa (job #3314747) | Cod sursa (job #660252) | Cod sursa (job #660265) | Cod sursa (job #660259) | Cod sursa (job #3314745)
#include <iostream>
#include <cstdio>
#include <vector>
using graph = std ::vector<std ::vector<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(const graph &G, std ::vector<bool> &used, const int node = 1)
{
used[node] = true;
for (const int &adj : G[node])
if (!used[adj])
dfs(G, used, adj);
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();
graph G((n + 1));
for (unsigned int i = 0; i < m; ++i)
{
unsigned int x = InParser ::get_unsigned_int(),
y = InParser ::get_unsigned_int();
G[x].push_back(y),
G[y].push_back(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(G, used, node);
printf("%d\n", answer);
return 0;
}