Pagini recente » Cod sursa (job #693278) | Cod sursa (job #673324) | Cod sursa (job #2600304) | Cod sursa (job #244321) | Cod sursa (job #3147236)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define magic_sauce inline __attribute__((always_inline))
magic_sauce int min( int a, int b ){ return a < b ? a : b; }
const int MAXN = 1e5;
const int MAXM = 2e5;
std::vector<int> adj[MAXN];
// componentele biconexe sunt componente conexe pe muchii
struct Edge{
int u, v;
} stack[MAXM];
int sp;
int highest[MAXN]; // cat de sus poate sa ajunga un nod din subarborele dfs al lui u
int dep[MAXN];
std::vector<int> comp[MAXN];
int ncomp;
void dumb_biconex( Edge e ){
do{
sp--;
comp[ncomp].push_back( stack[sp].u );
comp[ncomp].push_back( stack[sp].v );
}while( stack[sp].u != e.u || stack[sp].v != e.v );
std::sort( comp[ncomp].begin(), comp[ncomp].end() );
// eliminam duplicatele
int i, j = 0;
for( i = 1 ; i < (int)comp[ncomp].size() ; i++ )
if( comp[ncomp][i] != comp[ncomp][j] )
comp[ncomp][++j] = comp[ncomp][i];
comp[ncomp].erase( comp[ncomp].begin() + j + 1, comp[ncomp].end() );
ncomp++;
}
void dfs( int u, int p ){
highest[u] = dep[u];
for( int v : adj[u] ){
if( dep[v] < 0 ){ // nevizitat
dep[v] = 1 + dep[u];
stack[sp++] = Edge{ u, v };
dfs( v, u );
highest[u] = min( highest[u], highest[v] );
if( highest[v] >= dep[u] )
dumb_biconex( Edge{ u, v } ); // varsa tot din subarbore
}else if( v != u && dep[v] < dep[u] ){ // vizitat, mai sus
highest[u] = min( highest[u], dep[v] );
stack[sp++] = { u, v };
}
}
}
int main(){
FILE *fin = fopen( "biconex.in", "r" );
FILE *fout = fopen( "biconex.out", "w" );
int n, m, i, a, b;
fscanf( fin, "%d%d", &n, &m );
for( i = 0 ; i < m ; i++ ){
fscanf( fin, "%d%d", &a, &b );
adj[a - 1].push_back( b - 1 );
adj[b - 1].push_back( a - 1 );
}
for( i = 0 ; i < n ; i++ )
dep[i] = highest[i] = -1;
dep[0] = 0;
ncomp = 0;
dfs( 0, 0 );
fprintf( fout, "%d\n", ncomp );
for( i = 0 ; i < ncomp ; i++ ){
for( int v : comp[i] )
fprintf( fout, "%d ", v + 1 );
fputc( '\n', fout );
}
fclose( fin );
fclose( fout );
return 0;
}