Pagini recente » Cod sursa (job #2760269) | Cod sursa (job #2560636) | Cod sursa (job #2250109) | Cod sursa (job #2266158) | Cod sursa (job #647874)
Cod sursa(job #647874)
#include <fstream>
#include <vector>
#define maxn 100001
#define maxm 200001
using namespace std;
int n,m,k,poz;
bool viz[maxn];
vector <int> muchii[maxn],sol[maxn];
int nivelmin[maxn],nivel[maxn];
struct muchie
{
int a,b;
}leg[maxm];
void df(int nod,int tata)
{
int aux,i;
viz[nod]=1;
nivelmin[nod]=nivel[tata]+1;
nivel[nod]=nivel[tata]+1;
for(i=0;i<muchii[nod].size();i++)
{
aux=muchii[nod][i];
if(!viz[aux])
{
poz++;
leg[poz].a=nod;
leg[poz].b=aux;
df(aux,nod);
if(nivel[nod]<=nivelmin[aux])
{
k++;
while(leg[poz].a!=nod && leg[poz].b!=aux)
{
sol[k].push_back(leg[poz].b);
poz--;
}
sol[k].push_back(leg[poz].b);
sol[k].push_back(leg[poz].a);
poz--;
}
nivelmin[nod]=min(nivelmin[nod],nivelmin[aux]);
}
else
if(aux!=tata)
if(nivelmin[nod]>nivel[aux])
nivelmin[nod]=nivel[aux];
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(int j=0;j<=m;++j)
{
int x,y;
scanf("%d%d",&x,&y);
muchii[x].push_back(y);
muchii[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!viz[i]) df(i,.1);
printf("%d\n",k);
for(int i=1;i<=n;i++)
{
for(int j=sol[i].size()-1;j>=0;j--)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}