Pagini recente » Cod sursa (job #2516138) | Borderou de evaluare (job #707946) | Cod sursa (job #2343059) | Cod sursa (job #2239172) | Cod sursa (job #2886610)
// This program was written on 6.04.2022
// for problem biconex
// by Mircea Rebengiuc
#include <stdio.h>
#include <ctype.h>
#include <vector>
#define MAXN 100000
#define NIL -1
std::vector<int> adj[MAXN];
int root2comp[MAXN];
std::vector<int> comp[MAXN];
int ncomp;
int lvl[MAXN];// -1 daca nodul nu e pe stiva sau nivelul apelului
int viz[MAXN];
int dsu[MAXN];
int size[MAXN];
static inline int min( int a, int b ){
return a < b ? a : b;
}
int find( int u ){
if( dsu[u] == u )
return u;
return dsu[u] = find( dsu[u] );
}
void unite( int u, int v ){
u = find( u );
v = find( v );
if( u == v )
return;
if( size[u] < size[v] ){
dsu[u] = v;
size[v] += size[u];
}else{
dsu[v] = u;
size[u] += size[v];
}
}
int dfs( int root, int parrent ){
int lvlr = lvl[root], lvlv;
viz[root] = 1;
for( int v : adj[root] ){
if( !viz[v] ){
lvl[v] = lvl[root] + 1;
lvlv = dfs( v, root );
if( lvlv <= lvl[root] )
unite( root, v );
lvlr = min( lvlv, lvlr );
}else if( lvl[v] != NIL && v != parrent )
lvlr = min( lvl[v], lvlr );
}
lvl[root] = NIL;
return lvlr;
}
FILE *fin, *fout;
static inline int fgetint(){
int n = 0, ch;
while( !isdigit( ch = fgetc( fin ) ) );
do
n = n * 10 + ch - '0';
while( isdigit( ch = fgetc( fin ) ) );
return n;
}
int main(){
fin = fopen( "biconex.in", "r" );
fout = fopen( "biconex.out", "w" );
int n, m, i, a, b, root;
n = fgetint();
for( m = fgetint() ; m-- ; ){
a = fgetint() - 1;
b = fgetint() - 1;
adj[a].push_back( b );
adj[b].push_back( a );
}
lvl[0] = 0;
for( i = 0 ; i < n ; i++ ){
dsu[i] = i;
size[i] = 1;
}
dfs( 0, 0 );
ncomp = 0;
for( i = 0 ; i < n ; i++ ){
root = find( i );
if( size[root] > 1 ){
if( !root2comp[root] )
root2comp[root] = ++ncomp;
root = root2comp[root] - 1;
comp[root].push_back( i );
}
}
for( i = 0 ; i < n ; i++ ){
for( int j : adj[i] )
if( j > i && find( i ) != find( j ) ){
comp[ncomp].push_back( i );
comp[ncomp++].push_back( j );
}
}
fprintf( fout, "%d\n", ncomp );
for( i = 0 ; i < ncomp ; i++ ){
for( int j : comp[i] )
fprintf( fout, "%d ", j + 1 );
fputc( '\n', fout );
}
fclose( fin );
fclose( fout );
return 0;
}