Pagini recente » Cod sursa (job #340775) | Cod sursa (job #1379275) | Cod sursa (job #1592606) | Cod sursa (job #950900) | Cod sursa (job #2924806)
//#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fileIn("dfs.in");
ofstream fileOut("dfs.out");
class Graf {
int N;
int M;
vector<vector<int>> lista_ad;
public:
void citire();
void dfs(const int& nod, vector<int> &sel);
int nr_comp_conexe();
};
void Graf:: citire() {
int a, b;
fileIn>> N >> M;
// resize
lista_ad.resize(N + 1);
for(int i=1; i<= M; i++) {
fileIn >> a >> b;
//cout << a << b << "\n";
lista_ad[a].push_back(b);
lista_ad[b].push_back(a);
}
}
void Graf:: dfs(const int& nod, vector<int> &sel) {
sel[nod] = 1;
for(auto vecin : lista_ad[nod]) {
if(sel[vecin] == 0) {
dfs(vecin, sel);
}
}
}
int Graf:: nr_comp_conexe() {
int nr = 0;
vector<int> sel(N + 1,0);
for (int i = 1; i<= N; i++) {
if(sel[i] == 0) {
dfs(i, sel);
nr ++;
}
}
return nr;
}
int main() {
Graf my_graph;
my_graph.citire();
fileOut<< my_graph.nr_comp_conexe();
return 0;
}