Pagini recente » Cod sursa (job #3197683) | Cod sursa (job #1135065) | Cod sursa (job #501074) | Cod sursa (job #1868130) | Cod sursa (job #896991)
Cod sursa(job #896991)
#include<fstream>
#include<vector>
#include<cstring>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define Nmax 100009
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int j,nr,n,m,i,x,y,L[Nmax],T[Nmax],nivel[Nmax],ok[Nmax];
vector<int> a[Nmax],sol[Nmax];
vector<pair<int,int> >Q;
void DF(int nod)
{
vector<int>::iterator it;
int nod2;
ok[nod]=1;
for (it=a[nod].begin();it!=a[nod].end();it++)
{
nod2=*it;
if (!ok[nod2])
{
Q.pb(mp(nod,nod2));
nivel[nod2]=nivel[nod]+1;
T[nod2]=nod;
DF(nod2);
L[nod]=min(L[nod],L[nod2]);
}
else
L[nod]=min(L[nod],nivel[nod2]);
}
if (L[nod] >= nivel[T[nod]] && nod!=1)
{
nr++;
while (Q.back().first!=T[nod] || Q.back().second!=nod)
{
sol[nr].pb(Q.back().first);
sol[nr].pb(Q.back().second);
Q.pop_back();
}
Q.pop_back();
sol[nr].pb(nod);
sol[nr].pb(T[nod]);
}
}
int main()
{
in>>n>>m;
for (i=1;i<=m;i++)
{
in>>x>>y;
a[x].pb(y);
a[y].pb(x);
}
memset(L,0x3f3f3f3f,sizeof(L));
nivel[1]=1;
DF(1);
out<<nr<<'\n';
for (i=1;i<=nr;i++)
{
sort(sol[i].begin(),sol[i].end());
out<<sol[i][0]<<' ';
for (j=1;j<sol[i].size();j++)
if (sol[i][j]!=sol[i][j-1])
out<<sol[i][j]<<' ';
out<<'\n';
}
}