Pagini recente » Cod sursa (job #531533) | Cod sursa (job #2630032) | Cod sursa (job #1635677) | Cod sursa (job #1191025) | Cod sursa (job #2652002)
#include <bits/stdc++.h>
using namespace std;
ifstream f ( "biconex.in" );
ofstream g ( "biconex.out" );
int n, m, nivel[100005], mn[100005], stiva[100005], nr, tr;
bool fost[100005];
vector<int> vecini[100005], sol[100005];
stack <pair <int, int> > stk;
void dfs ( int nod, int tata )
{
fost[nod] = 1;
nivel[nod] = nivel[tata] + 1;
mn[nod] = nivel[nod];
for ( int i = 0; i < vecini[nod].size(); i++ )
if ( vecini[nod][i] != tata )
{
if ( fost[vecini[nod][i]] ) mn[nod] = min ( mn[nod], nivel[vecini[nod][i]] );
else
{
dfs ( vecini[nod][i], nod );
mn[nod] = min ( mn[nod], mn[vecini[nod][i]] );
}
}
}
void solve ( int nod, int tata )
{
fost[nod] = 1;
for ( int i = 0; i < vecini[nod].size(); i++ )
if ( !fost[vecini[nod][i]] )
{
stk.push( make_pair(nod,vecini[nod][i]) );
solve ( vecini[nod][i], nod );
if ( mn[ vecini[nod][i] ] >= nivel[ nod ] )
{
tr++;
while ( stk.top().first != nod )
{
sol[tr].push_back ( stk.top().first );
sol[tr].push_back ( stk.top().second );
stk.pop();
}
sol[tr].push_back ( stk.top().first );
sol[tr].push_back ( stk.top().second );
stk.pop();
}
}
}
int main()
{
f >> n >> m;
for ( int i = 1; i <= m; i++ )
{
int x, y;
f >> x >> y;
vecini[x].push_back ( y );
vecini[y].push_back ( x );
}
dfs ( 1, 0 );
for ( int i = 1; i <= n; i++ ) fost[i] = 0;
solve ( 1, 0 );
///for(int i=1;i<=n;i++) cout<<mn[i]<<' ';
g << tr << '\n';
while ( tr )
{
int v[100005];
for ( int i = 0; i < sol[tr].size(); i++ ) v[i] = sol[tr][i];
sort ( v, v + sol[tr].size() );
for ( int i = 0; i < sol[tr].size(); i++ ) if( v[i]!=v[i-1] ) g << v[i] << ' ';
tr--;
g << '\n';
}
}