Pagini recente » Cod sursa (job #2664951) | Cod sursa (job #882749) | Cod sursa (job #2429352) | Cod sursa (job #3230296) | Cod sursa (job #3249900)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
class Graf
{
public:
int N;
bool orientat;
vector<list<int>> listaAdiacenta;
vector<bool> vizitat;
int cateComponente=1;
vector<int> componente; //componente[i] = in a cata componenta e nodul i
Graf(int N, int orientat)
{
this->N = N;
this->orientat = orientat;
listaAdiacenta.resize(N + 1);
vizitat.assign(N + 1, false);
componente.resize(N+1);
}
// Adaugă o muchie între nodurile u și v
void AdaugaMuchie(int u, int v)
{
listaAdiacenta[u].push_back(v); // Adăugăm v în lista de adiacență a lui u
if(orientat==1)
listaAdiacenta[v].push_back(u); // Dacă graful este neorientat, adăugăm u în lista lui v
}
void AfisareListaAd()
{
for(int i=1; i<=N; i++)
//if(!listaAdiacenta[i].empty()) //daca lista nodului i nu e vida, o afisez
{
cout<<i<<" : ";
for(int nod : listaAdiacenta[i])
cout<<nod<<" ";
cout<<endl;
}
}
void DFS(int nod)
{
if(vizitat[nod]==true)
return;
vizitat[nod]=true;
componente[nod]=cateComponente;
for(int vecin : listaAdiacenta[nod])
DFS(vecin);
}
void GasesteComponente()
{
for(int i=1; i<=N; i++)
if(vizitat[i]==false)
{
cateComponente++;
DFS(i);
}
}
};
ifstream f("dfs.in");
ofstream g("dfs.out");
int main()
{
int N,M,u,v;
f>>N>>M;
Graf graf(N,1);
for(int i=0; i<M; i++)
{
f>>u>>v;
graf.AdaugaMuchie(u,v);
}
//Numarul componentelor conexe ale garfului
graf.DFS(1);
graf.GasesteComponente();
g<<graf.cateComponente;
return 0;
}