Pagini recente » Cod sursa (job #1810128) | Cod sursa (job #2898896) | Cod sursa (job #886253) | Cod sursa (job #422983) | Cod sursa (job #2794960)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int nodSursa;
int distante[100001];
class Graf {
private:
int m_nrNoduri;
vector<vector<int>> m_listAdiacenta;
vector<int> viz;
public:
void citire(){
ifstream f("../dfs.in");
vector<int> aux;
int nrMuchii;
f>>this->m_nrNoduri;
this->m_listAdiacenta.assign(this->m_nrNoduri + 1, aux);
f>>nrMuchii;
for(int i=0; i<nrMuchii; i++){
int x,y;
f>>x>>y;
this->m_listAdiacenta[x].push_back(y);
}
viz.assign(this->m_nrNoduri + 1, 0);
}
void prelucrare(int nod, int x){
//cout<<nod<<"\n";
distante[nod] = distante[x] + 1;
}
void BFS(int nod){
int curent;
queue<int> coada;
int viz[this->m_nrNoduri+1];
for(int i=1; i<=m_nrNoduri; i++){
viz[i] = 0;
}
coada.push(nod);
viz[nod] = 1;
prelucrare(nod, nod);
while(!coada.empty()){
curent = coada.front();
for(int i=0; i < this->m_listAdiacenta[curent].size(); i++){
if(viz[this->m_listAdiacenta[curent][i]] == 0){
coada.push(this->m_listAdiacenta[curent][i]);
prelucrare(coada.back(),curent);
viz[this->m_listAdiacenta[curent][i]] = 1;
}
}
coada.pop();
}
}
/*
void prelucrareDFS(int nod){
cout<<nod<<endl;
}
*/
void DFS(int nod){
//prelucrareDFS(nod);
viz[nod] = 1;
for(int i=0; i<this->m_listAdiacenta[nod].size(); i++){
if(viz[this->m_listAdiacenta[nod][i]] == 0){
DFS(this->m_listAdiacenta[nod][i]);
}
}
}
void afisDrumuri() {
ofstream g("../bfs.out");
for(int i=1; i <= this->m_nrNoduri; i++){
g<<distante[i] - 1<<" ";
}
}
int numaraComponenteConexe(){
int nr = 0;
for(int nod = 1; nod <= this->m_nrNoduri; nod++){
if(this->viz[nod] == 0){
nr++;
DFS(nod);
}
}
return nr;
}
};
int main() {
ofstream out("../dfs.out");
Graf g;
g.citire();
out<<g.numaraComponenteConexe();
return 0;
}