Pagini recente » Cod sursa (job #553122) | Cod sursa (job #765043) | Cod sursa (job #1678828) | Cod sursa (job #497919) | Cod sursa (job #1491401)
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, k;
bool a[4000][4000];
int viz[4000];
void bfs(int in) {
viz[in] = k;
queue<int> q;
q.push(in);
while(!q.empty()) {
in = q.front();
q.pop();
for(int i = 1; i <= n; i ++) {
if(a[in][i] && !viz[i]) {
viz[i] = k;
q.push(i);
}
}
}
}
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);
a[x][y] = true;
a[y][x] = true;
}
for(int i = 1; i <= n; i ++) {
if(!viz[i]) {
k ++;
bfs(i);
}
}
fprintf(g, "%d\n", k);
return 0;
}