Pagini recente » Cod sursa (job #2203058) | Cod sursa (job #2621590) | Cod sursa (job #2724042) | Cod sursa (job #3123549) | Cod sursa (job #2583279)
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMax = 1e5;
int N, M, NrC, Lev[NMax + 5], MinLev[NMax + 5];
bool A[NMax + 5], Use[NMax + 5];
vector <int> G[NMax + 5], Sol[NMax + 5];
stack <pair<int, int> > S;
void Process(int Nod)
{
int topX, topY;
++NrC;
do
{
topX = S.top().first, topY = S.top().second;
Sol[NrC].push_back(topY);
S.pop();
}
while(!S.empty() && topX != Nod && topY != Nod);
Sol[NrC].push_back(topX);
}
void DFS(int Nod, int Tata)
{
int nrSons = 0; Use[Nod] = 1;
Lev[Nod] = MinLev[Nod] = Lev[Tata] + 1;
for(auto Vecin : G[Nod])
{
if(!Use[Vecin])
{
S.push({Nod, Vecin});
DFS(Vecin, Nod);
MinLev[Nod] = min(MinLev[Nod], MinLev[Vecin]), nrSons++;
if(MinLev[Vecin] >= Lev[Nod])
Process(Nod);
}
else
MinLev[Nod] = min(MinLev[Nod], Lev[Vecin]);
}
}
int main()
{
fin >> N >> M;
for(int i = 1, x, y; i <= M; i++)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i = 1; i <= N; i++)
if(Use[i] == 0)
DFS(i, 0);
fout << NrC << '\n';
for(int i = 1; i <= NrC; i++)
{
for(auto x : Sol[i])
fout << x << " ";
fout << '\n';
}
fin.close();
fout.close();
return 0;
}