Pagini recente » Cod sursa (job #2280508) | Cod sursa (job #2299671) | Cod sursa (job #971559) | Cod sursa (job #154408) | Cod sursa (job #3352277)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct GrafNeorientat {
vector<vector<int>> v;
GrafNeorientat(int N) : v(N), vizitat(N) {}
void trasare(int a, int b) {
v[a].push_back(b);
v[b].push_back(a);
}
vector<int> vizitat;
int componente_conexe() {
int cate = 0;
for(int i=0; i<vizitat.size(); ++i) {
if(!vizitat[i]) {
dfs(i);
++cate;
}
}
return cate;
}
void dfs(int nod) {
vizitat[nod] = 1;
for(auto vecin: v[nod]) {
if(!vizitat[vecin]) {
dfs(vecin);
}
}
}
};
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M;
fin >> N >> M;
GrafNeorientat G(N);
for(int i=0; i<M; ++i) {
int a, b;
fin >> a >> b;
G.trasare(a-1, b-1);
}
fout << G.componente_conexe() << '\n';
return 0;
}