Pagini recente » Cod sursa (job #2584808) | Cod sursa (job #3221877) | Cod sursa (job #2779314) | Cod sursa (job #2783618) | Cod sursa (job #2133371)
#include <stack>
#include <vector>
#include <fstream>
#include <set>
#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 < int > q;
vector < int > w[nmax],ans[nmax];
set < int > s;
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 ] )
{
/// fout<<it<<endl;
/// q.push( );
q.push( it );
dfs( it , nod );
if( intorc[ it ] >= nivel[ nod ] )
{
crt++;
s.clear();
do
{
a = q.top();
q.pop();
if( s.find( a ) == s.end() )
{
ans[ crt ].push_back( a );
s.insert( a );
}
}while( a != 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';
}
}