Pagini recente » Cod sursa (job #62320) | Cod sursa (job #1422421) | Cod sursa (job #3256950) | Cod sursa (job #1349499) | Cod sursa (job #3249420)
///Componente Conexe - varianta iterativa
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<vector<int>> generare_lista_adiacenta(int varfuri, int muchii, int tip){
vector<vector<int>> lista(varfuri);
int x,y;
for(int i=0; i<muchii; i++){
fin>>x>>y;
lista[x-1].push_back(y);
if(tip==0)
lista[y-1].push_back(x);
}
return lista;
}
void DFS_iter(vector<vector<int>>& lista, int nod_start, vector<int>& componente, int cc){
stack<int> stiva;
stiva.push(nod_start);
componente[nod_start-1]=cc;
while(!stiva.empty()){
int nod=stiva.top();
stiva.pop();
for(auto vecin: lista[nod-1]){
if(componente[vecin-1]==0){
stiva.push(vecin);
componente[vecin-1]=cc;
}
}
}
}
int main()
{
int n,m;
fin>>n>>m;
vector<vector<int>> lista_adiacenta = generare_lista_adiacenta(n,m,0);
vector<int> componente(n,0);
int cc=0;
for(int i=0; i<n; i++){
if(componente[i]==0){
cc++;
DFS_iter(lista_adiacenta, i+1, componente, cc);
}
}
// for(int i=0; i<n; i++)
// fout<<componente[i]<<" ";
// fout<<'\n'<<cc<<'\n';
fout<<cc<<'\n';
return 0;
}