Pagini recente » Cod sursa (job #2940950) | Cod sursa (job #639063) | Cod sursa (job #2224548) | Cod sursa (job #1145755) | Cod sursa (job #2790438)
#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 NrComp;
int nivelInArbDFS[NMAX];
int nivelMinVecini[NMAX];
bool vizitat[NMAX];
void Dfs(int nod)
{
vizitat[nod] = true;
nivelMinVecini[nod] = NMAX;
for (int vecin : Adiacenta[nod])
{
if (!vizitat[vecin])
{
Stiva[++stVf] = {nod, vecin};
nivelInArbDFS[vecin] = nivelInArbDFS[nod] + 1;
Dfs(vecin);
}
if (nivelInArbDFS[vecin] < nivelMinVecini[nod])
nivelMinVecini[nod] = nivelInArbDFS[vecin];
}
}
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);
}
for (int i = 1; i <= N; ++i)
if (!vizitat[i])
{
stVf = 0;
nivelInArbDFS[i] = 1;
Dfs(i);
if (stVf == 0)
{
++NrComp;
compBic.push_back({i});
}
else
while (stVf)
{
++NrComp;
int nod = Stiva[stVf].second;
compBic.push_back({nod});
int idx = compBic.size() - 1;
while (stVf && nivelInArbDFS[ Stiva[stVf].first ] > nivelMinVecini[nod])
{
compBic[idx].push_back( Stiva[stVf].first );
--stVf;
}
compBic[idx].push_back( Stiva[stVf].first );
--stVf;
}
}
g << NrComp << '\n';
for (int i = 0; i < compBic.size(); ++i)
{
for(int j = 0; j < compBic[i].size(); ++j)
g << compBic[i][j] << ' ';
g << '\n';
}
return 0;
}