Pagini recente » Cod sursa (job #1194702) | Cod sursa (job #2063434) | Cod sursa (job #1643707) | Cod sursa (job #35789) | Cod sursa (job #2792573)
#include <bits/stdc++.h>
using namespace std;
class Graf {
private:
int nr_noduri;
int nr_muchii;
vector<vector<int>> lista_vecini;
public:
Graf();
Graf(int nr_noduri, int nr_muchii);
~Graf();
void graf_neorientat(istream &fis_sursa);
void DFS(int nod, vector<bool> &vizitat);
int comp_conexe();
};
Graf::Graf()
{
nr_noduri = 0;
nr_muchii = 0;
}
Graf::Graf(int nr_noduri_fis, int nr_muchii_fis)
{
vector<int> v(1,-1);
nr_noduri = nr_noduri_fis;
nr_muchii = nr_muchii_fis;
for(int i = 1; i <= nr_noduri; i++)
lista_vecini.push_back(v);
}
Graf::~Graf()
{
nr_noduri = 0;
nr_muchii = 0;
lista_vecini.clear();
}
void Graf::graf_neorientat(istream &fis_sursa)
{
int a, b;
for(int i = 1; i <= nr_muchii; i++)
{
fis_sursa >> a >> b;
lista_vecini[a].push_back(b);
lista_vecini[b].push_back(a);
}
}
void Graf::DFS(int nod, vector<bool> &viz)
{
viz[nod] = 1;
for(int i = 1; i < lista_vecini[nod].size(); i++)
if(viz[lista_vecini[nod][i]] == 0)
DFS(i, viz);
}
int Graf::comp_conexe()
{
int nr = 0;
vector<bool> viz(nr_noduri + 1, 0);
for(int i = 1; i <= nr_noduri; i++)
if(!viz[i])
{
nr++;
DFS(i, viz);
}
return nr;
}
void pb2_DFS()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
int N, M;
f >> N >> M;
Graf graf(N, M);
graf.graf_neorientat(f);
g << graf.comp_conexe();
f.close();
g.close();
}
int main() {
pb2_DFS();
return 0;
}