Pagini recente » Cod sursa (job #407612) | Cod sursa (job #1708943) | Cod sursa (job #2004277) | Cod sursa (job #3150370) | Cod sursa (job #2785226)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("dfs.in");
ofstream out("dfs.out");
const int maxim = 100001;
bool vizitate[maxim];
class Graf{
int noduri, muchii;
//lista de adiacenta
vector<int> listaAdiacenta[maxim];
public:
void construieste(int start, int final);
Graf(int noduri, int muchii);
int numaraConexe();
void dfs(int nodCurent);
};
void Graf::construieste(int start, int final) {
listaAdiacenta[start].push_back(final);
listaAdiacenta[final].push_back(start);
}
Graf::Graf(int noduri, int muchii) : noduri(noduri), muchii(muchii) {}
int Graf::numaraConexe() {
int componenteConexe = 0;
for(int i=1; i<noduri+1; i++)
{
if(!vizitate[i])
{
componenteConexe++;
dfs(i);
}
}
return componenteConexe;
}
void Graf::dfs(int nodCurent) {
vizitate[nodCurent] = true;
for(int vecin : listaAdiacenta[nodCurent])
{
if(!vizitate[vecin])
{
vizitate[vecin]=true;
dfs(vecin);
}
}
}
int main() {
int noduri, muchii, x, y;
std::fill(std::begin(vizitate), std::begin(vizitate)+maxim, false);
in>>noduri>>muchii;
Graf mygraf(noduri, muchii);
for(int i=0; i<muchii; i++)
{
//muchie de la x la y si de la y la x
in>>x>>y;
mygraf.construieste(x, y);
}
out<<mygraf.numaraConexe();
return 0;
}