Pagini recente » Cod sursa (job #2890682) | Cod sursa (job #53444) | Cod sursa (job #983785) | Cod sursa (job #2457924) | Cod sursa (job #2517421)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m;
int vf[400001],urm[400001],last[100001],nrg;
int nivel[100001],minNivel[100001];
bitset <100001> viz;
int coada[100001],nrc;
vector <int> sol[100001];
int nrs;
void adauga(int nod,int vec)
{
vf[++nrg]=vec;
urm[nrg]=last[nod];
last[nod]=nrg;
}
void dfsBic(int nod,int from,int niv=1)
{
viz[nod]=1;
nivel[nod]=niv;
minNivel[nod]=niv;
coada[++nrc]=nod;
for(int k=last[nod];k;k=urm[k])
if(vf[k]!=from && viz[ vf[k] ])
minNivel[nod]=min(minNivel[nod],nivel[ vf[k] ]);
else
{
dfsBic(vf[k],nod,niv+1);
minNivel[nod]=min(minNivel[nod],minNivel[ vf[k] ]);
if(nivel[ nod ]<=minNivel[ vf[k] ])
{
nrs++;
while(coada[nrc]!=nod)
sol[nrs].push_back(coada[nrc--]);
sol[nrs].push_back(nod);
}
}
}
int main()
{
in>>n>>m;
for(int i,j,k=1;k<=m;k++)
{
in>>i>>j;
adauga(i,j);
adauga(j,i);
}
dfsBic(1,0);
out<<nrs<<'\n';
for(int i=1;i<=nrs;i++)
{
for(int j=0;j<sol[i].size();j++)
out<<sol[i][j]<<' ';
out<<'\n';
}
return 0;
}