Pagini recente » info.conc.sept.2 | Monitorul de evaluare | Cod sursa (job #1949056) | Cod sursa (job #1136564) | Cod sursa (job #2793090)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <bitset>
using namespace std;
const int NMAX = 100001;
class graf{
private:
int nrNoduri, nrMuchii;
vector<int> listaAd[NMAX];
bitset<NMAX> viz;
vector<vector<int>> compBiconexe;
void dfsCompBiconexe(int nod, int nivelCrt, vector<int> &nivel, vector<int> &nivelMin, stack<int> &s);
public:
graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {};
void adaugaInListaAd(const int &nod1, const int &nod2);
vector<vector<int>> componenteBiconexe();
};
void graf::adaugaInListaAd(const int &nod1, const int &nod2) {
listaAd[nod1].push_back(nod2);
listaAd[nod2].push_back(nod1);
}
vector<vector<int>> graf :: componenteBiconexe() {
vector<int> nivel;
vector<int> nivelMin;
nivel.resize(NMAX);
nivelMin.resize(NMAX);
stack<int> s;
dfsCompBiconexe(1, 1, nivel, nivelMin, s);
return compBiconexe;
}
void graf::dfsCompBiconexe(int nod, int nivelCrt, vector<int> &nivel, vector<int> &nivelMin, stack<int> &s) {
viz[nod] = true;
s.push(nod);
nivel[nod] = nivelCrt;
nivelMin[nod] = nivelCrt;
for(int i = 0; i < listaAd[nod].size(); i++){
int vecin = listaAd[nod][i];
if(!viz[vecin]){
dfsCompBiconexe(vecin, nivelCrt + 1, nivel, nivelMin, s);
nivelMin[nod] = min(nivelMin[nod], nivelMin[vecin]);
if(nivelMin[vecin] >= nivel[nod]){
vector<int> compCrt;
int nodCompCrt;
do{
nodCompCrt = s.top();
compCrt.push_back(nodCompCrt);
s.pop();
}while(nodCompCrt != vecin);
compCrt.push_back(nod);
compBiconexe.push_back(compCrt);
}
}
else{
nivelMin[nod] = min(nivelMin[nod], nivel[vecin]);
}
}
}
int main() {
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
fin >> n >> m;
graf G(n, m);
for(int i = 0; i < m; i ++){
int n1, n2;
fin >> n1 >> n2;
G.adaugaInListaAd(n1, n2);
}
vector<vector<int>> componente = G.componenteBiconexe();
fout<<componente.size()<<"\n";
for(int i = 0; i < componente.size(); i++) {
for(int j = 0; j < componente[i].size(); j++) {
fout<<componente[i][j]<<" ";
}
fout<<"\n";
}
return 0;
}