Pagini recente » Cod sursa (job #626166) | Cod sursa (job #1895603) | Cod sursa (job #1686756) | Cod sursa (job #2756292) | Cod sursa (job #2651470)
#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];
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;
stiva[++nr] = nod;
for ( int i = 0; i < vecini[nod].size(); i++ )
if ( !fost[vecini[nod][i]] )
{
solve ( vecini[nod][i], nod );
if ( mn[ vecini[nod][i] ] >= nivel[ nod ] )
{
tr++;
while ( stiva[nr] != nod && nr )
{
sol[tr].push_back ( stiva[nr--] );
}
sol[tr].push_back ( nod );
}
}
}
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 )
{
for ( int i = 0; i < sol[tr].size(); i++ ) g << sol[tr][i] << ' ';
tr--;
g << '\n';
}
}