Pagini recente » Cod sursa (job #3284731) | Cod sursa (job #619212) | Cod sursa (job #578845) | Cod sursa (job #1781663) | Cod sursa (job #2133353)
#include <stack>
#include <vector>
#include <fstream>
#define nmax 100005
#define x first
#define y second
using namespace std;
ofstream fout ("biconex.out");
ifstream fin ("biconex.in");
int nivel[nmax],intorc[nmax],a,b,crt,i,n,m;
stack < pair < int , int > > q;
vector < int > w[nmax],ans[nmax];
void dfs( int nod , int parinte )
{
nivel[ nod ] = intorc[ nod ] = nivel[ parinte ] + 1;
///cout<<nod<<" "<<parinte<<'\n';
for( auto it : w[ nod ] )
{
if( it != parinte )
{
if( !nivel[ it ] )
{
q.push( make_pair( nod , it ) );
dfs( it , nod );
if( intorc[ it ] >= nivel[ nod ] )
{
crt++;
do
{
a = q.top().x;
b = q.top().y;
q.pop();
ans[ crt ].push_back( b );
}while( a != nod && b != it );
ans[ crt ].push_back( nod );
}
}
///cout<<it<<endl;
intorc[ nod ] = min( intorc[ nod ] , intorc[ it ] );
}
}
}
int main()
{
fin>>n>>m;
for( i = 1 ; i <= m ; i++ )
{
fin>>a>>b;
w[ a ].push_back( b );
w[ b ].push_back( a );
///cout<<a<<" "<<b<<endl;
}
dfs( 1 , 0 );
fout<<crt<<'\n';
for( i = 1 ; i <= crt ; i++ )
{
for( auto it : ans[ i ] )
fout<<it<<" ";
fout<<'\n';
}
}