Pagini recente » Istoria paginii utilizator/foxy55 | Profil CobuzCezar | Diferente pentru tabele-hash-prezentare-detaliata intre reviziile 9 si 8 | Istoria paginii utilizator/alexpaul100 | Cod sursa (job #2742456)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define pb push_back
#define nl '\n'
#define pii pair<int,int>
#define mp make_pair
using namespace std;
ifstream f ( "biconex.in" );
ofstream g ( "biconex.out" );
const int NMAX = 100005, MMAX = 2 * NMAX;
pii m[MMAX];
stack<pii>S;
vector<int>G[NMAX];
int dfn[NMAX], low[NMAX];
int compbiconex[MMAX], nrcomp;
vector<vector<int>>C;
void Stergmuchii ( int x, int y )
{
nrcomp++;
int tx, ty;
vector<int>comp;
do
{
tx = S.top().first;
ty = S.top().second;
S.pop();
if ( compbiconex[tx] != nrcomp )
{
compbiconex[tx] = nrcomp;
comp.pb ( tx );
}
if ( compbiconex[ty] != nrcomp )
{
compbiconex[ty] = nrcomp;
comp.pb ( ty );
}
}
while ( tx != x || ty != y );
C.pb ( comp );
}
void DFS ( int x, int father, int number )
{
dfn[x] = number;
low[x] = number;
for ( auto i : G[x] )
{
if ( i == father )
continue;
if ( dfn[i] == -1 )
{
S.push ( mp ( x, i ) );
DFS ( i, x, number + 1 );
low[x] = min ( low[x], low[i] );
if ( low[i] >= dfn[x] )
Stergmuchii ( x, i );
}
else low[x] = min ( low[x], low[i] );
}
}
int main()
{
int N, M;
f >> N >> M;
for ( int i = 1; i <= M; i++ )
{
int x, y;
f >> x >> y;
G[x].pb ( y );
G[y].pb ( x );
}
for ( int i = 1; i <= N; i++ )
dfn[i] = -1;
DFS ( 1, 0, 0 );
g << C.size() << nl;
for ( auto i : C )
{
for ( auto j : i )
g << j << ' ';
g << nl;
}
return 0;
}