Pagini recente » Cod sursa (job #496337) | Cod sursa (job #2405635) | Cod sursa (job #623262) | Cod sursa (job #2708183) | Cod sursa (job #2144127)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
void read(int &n, int &m, vector<int> **G) {
ifstream f("bfs.in");
if(!f.is_open()){
cout<<"The file can't be opened!\n";
exit(EXIT_FAILURE);
}
f>>n>>m;
(*G) = new vector<int>[n + 1];
int x, y;
for(int i = 0; i < m; ++i) {
f>>x>>y;
(*G)[x].push_back(y);
(*G)[y].push_back(x);
}
f.close();
}
void DFS(vector<int> *G, int *vis, int x) {
vis[x] = 1;
for(vector<int>::iterator it = G[x].begin(); it != G[x].end(); ++it) {
if(vis[*it] == 0) {
DFS(G, vis, *it);
}
}
}
int main() {
int n, m, answer = 0;
vector<int> *G = NULL;
read(n, m, &G);
int *vis = new int[n + 2];
fill(vis, vis + n + 1, 0);
for(int i = 1; i <= n; ++i) {
if(vis[i] == 0) {
DFS(G, vis, i);
++answer;
}
}
ofstream g("bfs.out");
if(!g.is_open()) {
cout<<"The file can't be opened!\n";
exit(EXIT_FAILURE);
}
g<<answer<<'\n';
g.close();
//Free up memory
delete[] vis;
for(int i = 1; i <= n; ++i) {
G[i].clear();
}
delete[] G;
return 0;
}