Pagini recente » Cod sursa (job #2780037) | Cod sursa (job #598631) | Cod sursa (job #2500117) | Cod sursa (job #2170339) | Cod sursa (job #1491390)
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, k;
int viz[100005];
int L[100005];
int vec[200005];
int urm[200005];
void bfs(int in) {
queue<int> q;
q.push(in);
viz[in] = k;
while(!q.empty()) {
in = q.front();
q.pop();
for(int poz = L[in]; poz; poz = urm[poz]) {
if(!viz[vec[poz]]) {
q.push(vec[poz]);
viz[vec[poz]] = k;
}
}
}
}
int main()
{
FILE *f = fopen("dfs.in", "r");
FILE *g = fopen("dfs.out", "w");
fscanf(f, "%d %d", &n, &m);
for(int i = 1; i <= m; i ++) {
fscanf(f, "%d %d", &x, &y);
vec[i * 2 - 1] = y;
urm[i * 2 - 1] = L[x];
L[x] = i * 2 - 1;
vec[i * 2] = x;
urm[i * 2] = L[y];
L[y] = i * 2;
}
for(int i = 1; i <= n; i ++) {
if(!viz[i]) {
k ++;
bfs(i);
}
}
fprintf(g, "%d\n", k);
return 0;
}