Pagini recente » Cod sursa (job #3324019) | Cod sursa (job #2038313) | Cod sursa (job #886380) | Cod sursa (job #737514) | Cod sursa (job #1268397)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5 + 2;
vector <int> G[Nmax];
vector <int> CB[Nmax];
stack < pair<int,int> > ST;
int low[Nmax], dfn[Nmax];
int vis[Nmax];
int N, M, B;
void biconex( int nod, int x )
{
B++;
pair<int,int> p;
do
{
p = ST.top();
ST.pop();
CB[B].push_back( p.first );
CB[B].push_back( p.second );
} while ( p.first != nod || p.second != x );
}
void DFS( int nod, int nr )
{
low[nod] = dfn[nod] = nr;
vis[nod] = 1;
for ( auto x: G[nod] )
{
if ( !vis[x] )
{
ST.push( pair<int,int>( nod, x ) );
DFS( x, nr + 1 );
low[nod] = min( low[nod], low[x] );
if ( low[x] >= dfn[nod] )
{
biconex( nod, x );
}
}
else
{
low[nod] = min( low[nod], dfn[x] );
}
}
}
void print()
{
ofstream g("biconex.out");
g << B << "\n";
for ( int i = 1; i <= B; ++i )
{
sort( CB[i].begin(), CB[i].end() );
CB[i].erase( unique( CB[i].begin(), CB[i].end() ), CB[i].end() );
for ( unsigned j = 0; j < CB[i].size(); ++j )
g << CB[i][j] << " ";
g << "\n";
}
g.close();
}
void read()
{
ifstream f("biconex.in");
f >> N >> M;
for ( int i = 1, a, b; i <= M; ++i )
{
f >> a >> b;
G[a].push_back( b );
G[b].push_back( a );
}
for ( int i = 1; i <= N; ++i )
dfn[i] = -1;
f.close();
}
int main()
{
read();
DFS( 1, 1 );
print();
return 0;
}