Pagini recente » Cod sursa (job #2630036) | Cod sursa (job #763563) | Cod sursa (job #1413472) | Cod sursa (job #2047057) | Cod sursa (job #1130710)
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
#define vecin v[nod][j]
#define nmax 100005
using namespace std;
int n,i,j,k,x,y,level[nmax],nivel[nmax],m,rez;
vector<int>v[nmax],sol[nmax];
stack<int>s;
void adauga_componenta_biconexa(int nodx,int nody)
{
rez++;
while (s.top()!=nody)
{
sol[rez].push_back(s.top());
s.pop();
}
sol[rez].push_back(nody);
sol[rez].push_back(nodx);
s.pop();
}
void df(int nod,int tata)
{
nivel[nod]=nivel[tata]+1;
level[nod]=nivel[nod];
for (int j=0;j<v[nod].size();j++)
if (!nivel[vecin])
{
s.push(vecin);
df(vecin,nod);
level[nod]=min(level[nod],level[vecin]);
if (level[vecin]>=nivel[nod])
adauga_componenta_biconexa(nod,vecin);
}else
if (vecin!=tata)
level[nod]=min(level[nod],nivel[vecin]);
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++)
scanf("%d %d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (i=1;i<=n;i++)
if (!nivel[i])
{
s.push(1);
df(i,0);
s.pop();
}
printf("%d\n",rez);
for (i=1;i<=rez;i++)
{
for (j=0;j<sol[i].size();j++)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}