Pagini recente » Cod sursa (job #2731834) | Cod sursa (job #289495) | Cod sursa (job #2131669) | Cod sursa (job #1129858) | Cod sursa (job #2368806)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin( "biconex.in" );
ofstream fout( "biconex.out" );
const int NMAX = 100005;
int N, M;
vector <int> Ad[NMAX];
stack <int> S;
int disc[NMAX];
int low[NMAX];
int t;
int nr_comp;
bool viz[NMAX];
vector <int> Comp[NMAX];
void read()
{
fin >> N >> M;
int i, x, y;
for ( i = 1; i <= M; ++i )
{
fin >> x >> y;
Ad[x].push_back( y );
Ad[y].push_back( x );
}
fin.close();
}
void DFS( int nod, int parent )
{
disc[nod] = low[nod] = ++t;
int i, w;
for ( i = 0; i < Ad[nod].size(); ++i )
{
w = Ad[nod][i];
if ( w == parent ) continue;
if ( !disc[w] )
{
S.push( w );
DFS( w, nod );
low[nod] = min( low[nod], low[w] );
if ( low[w] >= disc[nod] )
{
++nr_comp;
S.push( nod );
while ( !S.empty() && S.top() != w )
{
Comp[nr_comp].push_back( S.top() );
S.pop();
}
if ( !S.empty() )
{
Comp[nr_comp].push_back( S.top() );
S.pop();
}
}
}
else if ( w != parent )
low[nod] = min( low[nod], disc[w] );
}
}
void solve()
{
int i, j;
DFS( 1, 0 );
fout << nr_comp << '\n';
for ( i = 1; i <= nr_comp; ++i )
{
for ( j = 0; j < Comp[i].size(); ++j )
fout << Comp[i][j] << ' ';
fout << '\n';
}
}
int main()
{
read();
solve();
fout.close();
return 0;
}