Pagini recente » Cod sursa (job #2482030) | Cod sursa (job #256930) | Cod sursa (job #1177922) | Cod sursa (job #2804829) | Cod sursa (job #2791775)
#include <fstream>
#include <vector>
#include <utility>
#define NMAX 100009
std::vector<int> Adiacenta[NMAX];
std::vector< std::vector<int> > compBic;
std::pair<int, int> Stiva[NMAX * 2];
int stVf;
int nivelInArbDFS[NMAX]; // folosit si ca vizitat[]
int nivelMinVecini[NMAX];
void Dfs(int nod, int parinte)
{
nivelInArbDFS[nod] = nivelInArbDFS[parinte] + 1;
nivelMinVecini[nod] = NMAX;
for (int& vecin : Adiacenta[nod])
{
if (nivelInArbDFS[vecin]) // daca e vizitat
{
if (nivelMinVecini[nod] > nivelInArbDFS[vecin] && vecin != parinte)
nivelMinVecini[nod] = nivelInArbDFS[vecin];
}
else
{
Stiva[++stVf] = {nod, vecin};
Dfs(vecin, nod);
if (nivelMinVecini[nod] > nivelMinVecini[vecin])
nivelMinVecini[nod] = nivelMinVecini[vecin];
if (nivelMinVecini[vecin] >= nivelInArbDFS[nod])
{
compBic.push_back( {Stiva[stVf].second} );
while (Stiva[stVf].first != nod)
compBic.back().push_back(Stiva[stVf--].first);
compBic.back().push_back(Stiva[stVf--].first);
}
}
}
}
int main()
{
std::ifstream f("biconex.in");
std::ofstream g("biconex.out");
int N, M;
f >> N >> M;
for (int x, y, i = 0; i < M; ++i)
{
f >> x >> y;
Adiacenta[x].push_back(y);
Adiacenta[y].push_back(x);
}
nivelInArbDFS[1] = 1;
Dfs(1, 0);
g << compBic.size() << '\n';
for (auto& comp : compBic)
{
for (int& nod : comp)
g << nod << ' ';
g << '\n';
}
return 0;
}