Pagini recente » Cod sursa (job #1345676) | Cod sursa (job #1178480) | Cod sursa (job #1962505) | Cod sursa (job #767234) | Cod sursa (job #926478)
Cod sursa(job #926478)
#include <stdio.h>
#define nmax 100001
#include <vector>
#include <queue>
using namespace std;
vector <int> G[nmax];
queue <int> q;
int ok[nmax], count;
int main() {
freopen ("dfs.in", "r", stdin);
freopen ("dfs.out", "w", stdout);
int N, M, i, m, a, b, x;
scanf ("%d %d", &N, &M);
for (i = 1; i <= M; ++i) {
scanf ("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
for (i = 1; i <= N; ++i)
if (!ok[i]) {
++count;
q.push(i);
ok[i] = 1;
while (!q.empty()) {
x = q.front();
q.pop();
m = G[x].size();
for (int j = 0; j < m; ++j) {
if (!ok[G[x][j]]) {
ok[G[x][j]] = 1;
q.push(G[x][j]);
}
}
}
}
printf ("%d", count);
return 0;
}