Pagini recente » Cod sursa (job #2923175) | Cod sursa (job #3285595) | Cod sursa (job #3258138) | Cod sursa (job #1214461) | Cod sursa (job #146288)
Cod sursa(job #146288)
#include <stdio.h>
#include <assert.h>
#include <vector>
using namespace std;
#define ll long long
#define minim(a, b) ((a < b) ? a : b)
int N, M, uz[100005], conex;
vector<int> G[100005];
void df(int nod)
{
int i, sz, x;
uz[nod] = 1;
for (sz = G[nod].size(), i = 0; i < sz; ++i)
if (!uz[x = G[nod][i]])
df(x);
}
int main(void)
{
int i, j;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d", &N, &M);
assert(1 <= N && N <= 100000);
assert(0 <= M && M <= minim((ll)N * (N+1)/2, 200000));
for (; M; --M)
{
scanf("%d %d", &i, &j);
assert(1 <= i && i <= N);
assert(1 <= j && j <= N);
G[i].push_back(j);
G[j].push_back(i);
}
for (i = 1; i <= N; i++)
if (!uz[i])
{
++conex;
df(i);
}
printf("%d\n", conex);
return 0;
}