Pagini recente » Cod sursa (job #1053661) | Cod sursa (job #965988) | Cod sursa (job #1239850) | Istoria paginii runda/oji_sim2 | Cod sursa (job #2679180)
#include <fstream>
#include <vector>
#define f in
#define g out
using namespace std;
ifstream in ( "biconex.in" );
ofstream out( "biconex.out" );
int n, m, i, x, y, cbc;
int low[100100], viz[100100], niv[100100];
vector<int> L[100100], v, comp[100100];
void dfs ( int nod, int tata, int nivel ){
viz[nod] = 1;
low[nod] = niv[nod] = nivel;
v.push_back(nod);
for ( auto vecin : L[nod] ){
if ( vecin == tata )
continue;
if ( viz[vecin] ){
low[nod] = min ( low[nod], low[vecin] );
continue;
}
dfs(vecin, nod, nivel+1);
low[nod] = min ( low[nod], low[vecin] );
if ( low[vecin] >= niv[nod] ){
cbc++;
x = 0;
while ( x != vecin ) {
x = v.back();
v.pop_back();
comp[cbc].push_back(x);
}
comp[cbc].push_back(nod);
}
}
}
int main() {
f>>n>>m;
for ( i=1; i <= m; i++ ){
f>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
dfs ( 1, 0, 1 );
g<<cbc<<"\n";
for ( i=1; i <= cbc; i++, g<<"\n" )
for ( auto x : comp[i] )
g<<x<<" ";
return 0;
}