Pagini recente » Cod sursa (job #2348557) | Cod sursa (job #1014439) | Cod sursa (job #2699016) | Cod sursa (job #1014367) | Cod sursa (job #2788363)
#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<map>
#include<queue>
std::ifstream f("dfs.in");
std::ofstream fg("dfs.out");
int n, m, a, b;
class graf{
public:
int n, m;
graf(int n, int m);
std::map<int, bool> viz;
std::map<int, std::vector<int> > lista;
void new_lista( int nod1, int nod2);
void sortare_lista();
void dfs(int nod);
int componente_conexe();
};
graf::graf(int n, int m) {
this->n = n;
this->m = m;
}
void graf::new_lista(int nod1, int nod2){
lista[nod1].push_back(nod2);
lista[nod2].push_back(nod1);
//this->sortare_lista();
}
void graf::sortare_lista() {
for(auto i=1 ; i<n+1 ; i++)
std::sort(lista[i].begin(), lista[i].end());
}
void graf::dfs(int nod){
viz[nod] = true;
//std::cout<<nod<<" ";
for( auto i = lista[nod].begin(); i != lista[nod].end(); i++)
if(!viz[*i]) dfs(*i);
}
int graf::componente_conexe() {
int cnt = 0;
for(auto i = 1 ; i<=n ; i++ )
if( !viz[i] ){
cnt++;
dfs(i);
}
return cnt;
}
int main() {
f>>n>>m;
graf g(n, m);
for(int i=0 ; i<m ; i++){
f>>a>>b;
g.new_lista(a,b);
}
fg<<g.componente_conexe();
return 0;
}