Pagini recente » Cod sursa (job #2746261) | Cod sursa (job #2279346) | Cod sursa (job #1435231) | Rating 4e5hrbedrbsadvas (grgcucu) | Cod sursa (job #2796675)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graf{
private:
int n,m;
static const int N=100010;
vector<int> v[N];
bitset <N> viz;
public:
Graf();
~Graf();
void add_edge(int,int);
void dfs(int);
void read_Graf();
int nr_connected_components();
};
Graf::Graf() {
}
Graf::~Graf() {
}
void Graf::add_edge(int x, int y){
v[x].push_back(y);
v[y].push_back(x);
}
void Graf::dfs(int node){
viz[node] = 1;
for(auto it:v[node])
if(!viz[it])
dfs(it);
}
int Graf::nr_connected_components() {
int ct=0;
for(int i=1;i<=this->n;i++)
if(!viz[i]){
dfs(i);
ct++;
}
return ct;
}
void Graf::read_Graf(){
int nr_noduri,nr_muchii;
fin>>nr_noduri>>nr_muchii;
this->n = nr_noduri;
this->m = nr_muchii;
for(int i=1;i<=m;i++){
int x,y;
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
}
int main(){
Graf G;
G.read_Graf();
fout<<G.nr_connected_components();
return 0;
}