Pagini recente » Cod sursa (job #396091) | Cod sursa (job #1320464) | Cod sursa (job #1345976) | Cod sursa (job #419798) | Cod sursa (job #2530740)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n,m;
vector <int> gf[100001];
int nivel[100001],minNivel[100001];
bitset <100001> viz;
int stiva[100001],nrc;
vector <int> sol[100001];
int nrs;
void dfsBic(int nod,int from,int niv=1)
{
viz[nod]=1;
nivel[nod]=niv;
minNivel[nod]=niv;
stiva[++nrc]=nod;
for( auto vec:gf[nod] )
if( vec != from && viz[vec] )
{
minNivel[nod]=min( minNivel[nod], nivel[vec] ); //muchiile de intoarcere
}
else if( vec != from )
{
dfsBic( vec, nod, niv+1 );
minNivel[nod]=min( minNivel[nod], minNivel[vec] );
if( nivel[nod] <= minNivel[vec] )
{
nrs++;
while( stiva[nrc] != vec )
sol[nrs].push_back( stiva[nrc--] );
sol[nrs].push_back( stiva[nrc--] );
sol[nrs].push_back( nod );
}
}
}
int main()
{
in>>n>>m;
for(int i,j,k=1;k<=m;k++)
{
in>>i>>j;
gf[i].push_back(j);
gf[j].push_back(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;
}