Pagini recente » Cod sursa (job #1724837) | Cod sursa (job #1105541) | Cod sursa (job #2391437) | Cod sursa (job #38596) | Cod sursa (job #2796450)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
class Graf{
private:
bool orientat;
int nrNoduri;
int nrMuchii;
vector<vector<int>> listaAdiacenta;
void bfs(vector<int>& distante, vector<bool>& vizitat, int nodStart){
queue<int> coada;
coada.push(nodStart);
distante[nodStart] = 0;
while (coada.empty() == false){
int nodCurent = coada.front();
vizitat[nodCurent] = true;
for (auto i : listaAdiacenta[nodCurent]){
if (vizitat[i] == false){
coada.push(i);
distante[i] = distante[nodCurent] + 1;
vizitat[i] = true;
}
}
coada.pop();
}
}
void dfs(vector<bool>& vizitat, int nodCurent){
vizitat[nodCurent] = true;
for (auto i : listaAdiacenta[nodCurent])
if (vizitat[i] == false)
dfs(vizitat, i);
}
void dfsbiconex(int nodCurent, int nodAnterior, int adancimeCurenta, vector<vector<int>>& componente, stack<int>& stiva, vector<bool>& vizitat, vector<int>& adancime, vector<int>& adancimeMin){
adancime[nodCurent] = adancimeCurenta;
vizitat[nodCurent] = true;
adancimeMin[nodCurent] = adancimeCurenta;
stiva.push(nodCurent);
for (auto i : listaAdiacenta[nodCurent]){
if (i != nodAnterior){
if (vizitat[i] == true){
adancimeMin[nodCurent] = min(adancimeMin[nodCurent], adancime[i]);
}
else{
dfsbiconex(i, nodCurent, adancimeCurenta + 1, componente, stiva, vizitat, adancime, adancimeMin);
adancimeMin[nodCurent] = min(adancimeMin[nodCurent], adancimeMin[i]);
if(adancime[nodCurent] <= adancimeMin[i]){
vector<int> componenta;
componenta.push_back(nodCurent);
int nod = stiva.top();
stiva.pop();
componenta.push_back(nod);
while (i != nod){
nod = stiva.top();
stiva.pop();
componenta.push_back(nod);
}
componente.push_back(componenta);
}
}
}
}
}
public:
Graf(){
nrNoduri = 0;
nrMuchii = 0;
orientat = false;
vector<int> gol;
for (int i = 0; i < nrNoduri; i++)
listaAdiacenta.push_back(gol);
}
Graf(int nrNod, int nrMuc, bool esteOrientat){
nrNoduri = nrNod;
nrMuchii = nrMuc;
orientat = esteOrientat;
vector<int> gol;
for (int i = 0; i < nrNoduri; i++)
listaAdiacenta.push_back(gol);
}
bool getOrient(){
return orientat;
}
int getNrNoduri(){
return nrNoduri;
}
int getNrMuchii(){
return nrMuchii;
}
void setOrient(bool orient){
orientat = orient;
}
void setNrNoduri(int nr){
nrNoduri = nr;
}
void setNrMuchii(int nr){
nrMuchii = nr;
}
void setareGraf(){
if (orientat){
int x, y;
for(int i = 0; i < nrMuchii; i++){
fin >> x >> y;
x--;
y--;
listaAdiacenta[x].push_back(y);
}
}
else{
int x, y;
for(int i = 0; i < nrMuchii; i++){
fin >> x >> y;
x--;
y--;
listaAdiacenta[x].push_back(y);
listaAdiacenta[y].push_back(x);
}
}
}
vector<int> distanteMinime(int nodStart){
vector<int> distante(nrNoduri, -1);
vector<bool> vizitat(nrNoduri, false);
bfs(distante, vizitat, nodStart);
return distante;
}
int nrCompConexe(){
int nr = 0;
vector<bool> vizitat(nrNoduri, false);
for (int i = 0; i < nrNoduri; i++)
if (vizitat[i] == false){
dfs(vizitat, i);
nr++;
}
return nr;
}
vector<vector<int>> ComponenteBiconexe(){
vector<bool> vizitat(nrNoduri, false);
vector<int> adancime(nrNoduri, -1);
vector<int> adancimeMin(nrNoduri, -1);
stack<int> stiva;
vector<vector<int>> componente;
dfsbiconex(0, -1, 0, componente, stiva, vizitat, adancime, adancimeMin);
return componente;
}
};
int main(){
int n, m;
vector<vector<int>> componente;
fin >> n >> m;
Graf graf(n,m,false);
graf.setareGraf();
componente = graf.ComponenteBiconexe();
fout<<componente.size()<<"\n";
for (int i = 0; i < componente.size(); i++){
for (auto nd : componente[i]){
fout << nd+1 << " ";
}
fout<< "\n";
}
return 0;
}