Pagini recente » Cod sursa (job #2870663) | Cod sursa (job #2783202) | Cod sursa (job #2053926) | Cod sursa (job #837228) | Cod sursa (job #2788484)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graf
{
private:
int nrNoduri;
vector<vector<int>> matrAdiacenta;
public:
Graf(int N, vector<vector<int>> & matrice);
void BFS(int nodStart);
void DFS(int nodStart, vector<bool> &vizitat);
int nrCompConexe();
vector<vector <int>> getMatrAdiacenta()
{
return matrAdiacenta;
}
};
Graf :: Graf(int N, vector<vector<int>> & matrice)
{
nrNoduri = N;
matrAdiacenta = matrice;
}
void Graf :: BFS(int nodStart)
{
queue<int> Q;
int x, y;
vector<int> distanta(nrNoduri+1, -1);
distanta[nodStart] = 0;
Q.push(nodStart);
while (!Q.empty())
{
x = Q.front(); //eliminam nodul curent din coada
Q.pop();
for (int i = 1; i < matrAdiacenta[x].size(); ++i)
//daca nu au mai fost vizitati si a fost gasit astfel drum mai scurt
if (distanta[matrAdiacenta[x][i]] == -1)
{
distanta[matrAdiacenta[x][i]] = distanta[x] + 1;
Q.push(matrAdiacenta[x][i]);
}
}
for (int i = 1; i <= nrNoduri; ++i) {
fout << distanta[i] << " ";
}
}
void Graf :: DFS(int x, vector<bool> &vizitat)
{
vizitat[x] = 1;
for(int i = 1; i < matrAdiacenta[x].size(); i++)
if(vizitat[matrAdiacenta[x][i]] == 0)
DFS(matrAdiacenta[x][i], vizitat);
}
int Graf :: nrCompConexe()
{
int nrCompCon = 0;
vector<bool> vizitat(nrNoduri+1, 0);
for(int i = 1; i <= nrNoduri; ++i )
if(!vizitat[i]){
nrCompCon++;
DFS(i, vizitat);
}
return nrCompCon;
}
int main()
{ int N, M;
int x, y;
fin >> N >> M;
vector<vector<int>> matriceCitita;
vector<int> aux(1,-1);
matriceCitita.resize(N+1, aux);
for (int i = 1; i <= M; ++i){
fin >> x >> y;
matriceCitita[x].push_back(y);
matriceCitita[y].push_back(x);
}
Graf graf(N, matriceCitita);
/* for (int i = 1; i < graf.getMatrAdiacenta().size(); ++i){
for (int j = 1; j < graf.getMatrAdiacenta()[i].size(); ++j){
fout<< graf.getMatrAdiacenta()[i][j]<<" ";
}
fout<<"\n";
}*/
fout<<graf.nrCompConexe();
return 0;
}