Pagini recente » Clasament dupa rating | Istoria paginii utilizator/lilit | Clasament dupa rating | Atasamentele paginii Clasament simulare_de_oni_8 | Cod sursa (job #2893261)
// This program was written on 25.04.2022
// for problem ctc
// by Mircea Rebengiuc
#include <stdio.h>
#include <ctype.h>
#include <vector>
#define MAXN 100000
#define NIL -1
std::vector<int> adj[MAXN];
std::vector<int> comp[MAXN];
int ncomp;
int stack[MAXN];
int sp;
int lvli[MAXN];
int lvlm[MAXN];
int onstack[MAXN];
int lvl;
static inline int min( int a, int b ){
return a < b ? a : b;
}
void tarjan( int u ){
int v;
lvli[u] = lvlm[u] = lvl++;
stack[sp++] = u;
onstack[u] = 1;
for( int v : adj[u] ){// declaram in alt scope deci e ok
if( lvli[v] == NIL ){
tarjan( v );
lvlm[u] = min( lvlm[u], lvlm[v] );
}else if( onstack[v] ){
lvlm[u] = min( lvlm[u], lvli[v] );
}
}
if( lvli[u] == lvlm[u] ){// componenta noua
do{
v = stack[--sp];
onstack[v] = 0;
comp[u].push_back( v );
}while( v != u );
ncomp++;
}
}
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( "ctc.in", "r" );
fout = fopen( "ctc.out", "w" );
int n, m, i, a, b;
n = fgetint();
for( m = fgetint() ; m-- ; ){
a = fgetint() - 1;
b = fgetint() - 1;
adj[a].push_back( b );
}
lvl = 0;
for( i = 0 ; i < n ; i++ ){
lvli[i] = lvlm[i] = NIL;
onstack[i] = 0;
}
tarjan( 0 );
fprintf( fout, "%d\n", ncomp );
for( i = 0 ; i < n ; i++ )
if( comp[i].size() ){
for( int j : comp[i] )
fprintf( fout, "%d ", j + 1 );
fputc( '\n', fout );
}
fclose( fin );
fclose( fout );
return 0;
}