Pagini recente » Cod sursa (job #654276) | Cod sursa (job #327012) | Cod sursa (job #915168) | Cod sursa (job #1349553) | Cod sursa (job #1705422)
#include <stdio.h>
#include <vector>
#include <string.h>
#include <iostream>
#include <fstream>
#include <queue>
#define NMAX 100005
bool visited[NMAX];
int n, m;
std::vector<int> neighbors[NMAX];
void bfs (int source) {
std::queue<int> BFSQueue;
BFSQueue.push(source);
visited[source] = true;
int node;
while (!BFSQueue.empty()) {
node = BFSQueue.front();
BFSQueue.pop();
for (unsigned int i = 0; i < neighbors[node].size(); i++) {
if (!visited[neighbors[node][i]]) {
BFSQueue.push(neighbors[node][i]);
visited[neighbors[node][i]] = true;
}
}
}
}
int main() {
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int i, x, y;
fin >> n >> m;
for (i = 1; i <= m; i++)
{
fin >> x >> y;
neighbors[x].push_back(y);
neighbors[y].push_back(x);
}
memset(visited, false, NMAX * sizeof(bool));
int nrcomp = 0;
for (i = 1; i <= n; i++) {
if (!visited[i]) {
nrcomp++;
bfs(i);
}
}
fout << nrcomp << "\n";
return 0;
}