Pagini recente » Cod sursa (job #2540625) | Cod sursa (job #2671078) | Cod sursa (job #122701) | Cod sursa (job #2711515) | Cod sursa (job #1122240)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#define Nmax 100005
using namespace std;
int low[Nmax], nivel[Nmax], n, m;
stack<int> S;
vector<int> sol[Nmax];
vector<int> L[Nmax];
int nr;
void citire()
{
scanf("%d %d",&n, &m);
for (int i=1; i<=m; i++)
{
int x,y;
scanf("%d %d",&x, &y);
L[y].push_back(x);
L[x].push_back(y);
}
}
void adaugaComponentaBiconexa(int nod, int vecin)
{
++nr;
while(S.top() != vecin)
{
sol[nr].push_back(S.top());
S.pop();
}
sol[nr].push_back(nod);
sol[nr].push_back(vecin);
S.pop();
}
void df(int nod, int tata)
{
nivel[nod] = nivel[tata] + 1;
low[nod] = nivel[nod];
for (int i=0; i<L[nod].size(); i++)
{
int vecin = L[nod][i];
if (vecin == tata)
continue;
if (!nivel[vecin])
{
S.push(vecin);
df(vecin, nod);
low[nod] = min(low[nod], low[vecin]);
if (low[vecin] >= nivel[nod])
adaugaComponentaBiconexa(nod, vecin);
}
else
low[nod] = min(low[nod], nivel[vecin]);
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
for(int i=1; i<=n; i++)
if (!nivel[i])
{
S.push(i);
df(i, 0);
S.pop();
}
printf("%d\n",nr);
for (int i=1; i<=nr; i++)
{
for (int j=0; j<sol[i].size(); j++)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}