Pagini recente » Cod sursa (job #589562) | Cod sursa (job #356673) | Cod sursa (job #1877115) | Cod sursa (job #1248665) | Cod sursa (job #2797668)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int nmax = 100001;
class Graf
{
private:
bool orientat;
int nrNoduri;
vector <int> listaAdiacenta[nmax];
public:
Graf(int nrNoduri = 0, bool orientat = false);
int get_nrNoduri();
void citireMuchii(int nrMuchii);
vector<int> BFS(int start);
void DFS(int nodCurent, bool *vizitatDFS);
int nrComponenteConexe();
void DFSStiva(int nodcurent, bool *vizitatDFS, stack<int> &stivaTimp);
void sortareTopologica();
void TarjanCTC(int &timpCurent, int nodCurent, int *timpDescoperire, int *minimLegat, bool *estePeStiva, stack <int> &stiva, vector<vector<int>> &componenteTConexe);
void CTC();
void TarjanBC(int &timpCurent, int nodCurent, int parinte, int *timpDescoperire, int *minimLegat, stack <int> &stiva, vector<vector<int>> &componenteBConexe);
void BC();
};
Graf :: Graf(int nrNoduri, bool orientat) : nrNoduri(nrNoduri), orientat(orientat)
{
this->nrNoduri = nrNoduri;
this->orientat = orientat;
}
int Graf::get_nrNoduri()
{
return this->nrNoduri;
}
void Graf::citireMuchii(int nrMuchii)
{
int nod1, nod2;
for(int i = 0; i < nrMuchii; i++)
{
in >> nod1 >> nod2;
listaAdiacenta[nod1].push_back(nod2);
if(!orientat)
{
listaAdiacenta[nod2].push_back(nod1);
}
}
}
void Graf::TarjanBC(int &timpCurent, int nodCurent, int parinte, int *timpDescoperire, int *minimLegat, stack <int> &stiva, vector<vector<int>> &componenteBConexe)
{
stiva.push(nodCurent);
timpDescoperire[nodCurent] = timpCurent;
minimLegat[nodCurent] = timpCurent;
timpCurent++;
for(auto vecin:listaAdiacenta[nodCurent])
{
if(vecin != parinte)
{
if(timpDescoperire[vecin] == 0)
{
TarjanBC(timpCurent, vecin, nodCurent, timpDescoperire, minimLegat, stiva, componenteBConexe);
minimLegat[nodCurent] = min(minimLegat[nodCurent], minimLegat[vecin]);
if (timpDescoperire[nodCurent] <= minimLegat[vecin]) {
vector<int> componentaCurenta;
int aux;
componentaCurenta.push_back(nodCurent);
do {
aux = stiva.top();
componentaCurenta.push_back(aux);
stiva.pop();
} while (aux != vecin);
componenteBConexe.push_back(componentaCurenta);
}
}
else
{
minimLegat[nodCurent] = min(minimLegat[nodCurent], timpDescoperire[vecin]);
}
}
}
}
void Graf::BC()
{
int timpCurent = 1;
int timpDescoperire[nmax] = {0}, minimLegat[nmax] = {0};
bool estePeStiva[nmax] = {false};
stack <int> stiva;
vector <vector <int>> componenteBConexe;
TarjanBC(timpCurent, 1, -1, timpDescoperire, minimLegat, stiva, componenteBConexe);
out << componenteBConexe.size() << "\n";
for(auto x:componenteBConexe)
{
for(auto y:x)
{
out << y << " ";
}
out << "\n";
}
}
int main() {
int n, m;
in >> n >> m;
Graf g(n,false);
g.citireMuchii(m);
g.BC();
return 0;
}