Pagini recente » Cod sursa (job #570872) | Cod sursa (job #2260257) | Cod sursa (job #268237) | Cod sursa (job #1664360) | Cod sursa (job #2575539)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100005;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int T, N, M, x, y;
vector < int > Ad[NMAX];
int viz[NMAX], ct1;
int desc[NMAX];
int low[NMAX];
vector < int > n;
void DFS( int nod, int parent )
{
viz[nod] = 1;
low[nod] = desc[nod];
for( int i = 0; i < Ad[nod].size(); ++i )
{
int w = Ad[nod][i];
if( !viz[w] )
{
if( nod == 1 )ct1++;
desc[w] = 1 + desc[nod];
DFS( w, nod );
low[nod] = min( low[nod], low[w] );
}
else if( w != parent )
low[nod] = min( low[nod], desc[w] );
}
}
void Read()
{
fin >>
N >> M;
for( int i = 1; i <= M; ++i )
{
fin >> x >> y;
Ad[x].push_back( y );
Ad[y].push_back( x );
}
desc[1] = low[1] = 1;
//for( int i = 1; i <= N; ++i )fout << desc[i] << ' ' << low[i] << '\n';
}
stack < int > S;
vector < int > C[NMAX];
int nrc;
void DFSc( int nod, int parent )
{
viz[nod] = 1;
low[nod] = desc[nod];
for( int i = 0; i < Ad[nod].size(); ++i )
{
int w = Ad[nod][i];
if( !viz[w] )
{
S.push( w );
if( nod == 1 )ct1++;
desc[w] = 1 + desc[nod];
DFSc( w, nod );
low[nod] = min( low[nod], low[w] );
if( low[w] >= desc[nod] && w != parent )
{
S.push( nod );
nrc++;
while( S.size() && S.top() != w )
{
C[nrc].push_back( S.top() );
S.pop();
}
if( S.size() )
{
C[nrc].push_back( S.top() );
S.pop();
}
}
}
else if( w != parent )
low[nod] = min( low[nod], desc[w] );
}
}
void Componente()
{
DFSc( 1, 0 );
/*if( S.size() )nrc++;
while( S.size() )
{
C[nrc].push_back( S.top() );
S.pop();
}*/
fout << nrc << '\n';
for( int i = nrc; i >= 1; --i )
{
//fout << C[i].size() << ' ';
for( int j = 0; j < C[i].size(); ++j )
fout << C[i][j] << ' ';
fout << '\n';
}
}
bool vn[NMAX];
void DFSn( int nod, int parent )
{
viz[nod] = 1;
low[nod] = desc[nod];
for( int i = 0; i < Ad[nod].size(); ++i )
{
int w = Ad[nod][i];
if( !viz[w] )
{
if( nod == 1 )ct1++;
desc[w] = 1 + desc[nod];
DFSn( w, nod );
low[nod] = min( low[nod], low[w] );
if( low[w] >= desc[nod] && w != parent && nod != 1 && vn[nod] == 0 )
{n.push_back( nod ); vn[nod] = 1;}
}
else if( w != parent )
low[nod] = min( low[nod], desc[w] );
}
}
void Noduri()
{
DFSn( 1, 0 );
if( ct1 > 1 ) n.push_back( 1 );
fout << n.size() << '\n';
for( int i = n.size()-1 ; i >= 0 ; --i )
fout << n[i] << ' ';
}
vector < pair < int, int > > m;
void DFSm( int nod, int parent )
{
viz[nod] = 1;
low[nod] = desc[nod];
for( int i = 0; i < Ad[nod].size(); ++i )
{
int w = Ad[nod][i];
if( !viz[w] )
{
desc[w] = 1 + desc[nod];
DFSm( w, nod );
low[nod] = min( low[nod], low[w] );
if( low[w] > desc[nod] && w != parent )
m.push_back( {nod, w} );
}
else if( w != parent )
low[nod] = min( low[nod], desc[w] );
}
}
void Muchii()
{
DFSm( 1, 0 );
fout << m.size() << '\n';
for( int i = m.size()-1; i >= 0; --i )
fout << m[i].first << ' ' << m[i].second << '\n';
}
void Solve()
{
Componente();
}
int main()
{
Read();
Solve();
return 0;
}