Pagini recente » Monitorul de evaluare | Cod sursa (job #3293003) | Cod sursa (job #3293863) | Cod sursa (job #3292684) | Cod sursa (job #3293945)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
#ifndef HOME
ifstream fin( "biconex.in" );
ofstream fout( "biconex.out" );
#define cin fin
#define cout fout
#endif // HOME
vector<int> edges[NMAX+1];
int t = 0;
int timp[NMAX+1], low[NMAX+1];
bool viz[NMAX+1];
stack<int> stiva;
vector <int> components[NMAX+1];
int nrComp = 0;
void dfs( int node, int par = -1 ) {
low[node] = timp[node] = t++;
viz[node] = true;
stiva.push( node );
for( auto vec: edges[node] ) {
if( !viz[vec] ) {
dfs( vec, node );
low[node] = min( low[node], low[vec] );
if( low[vec] >= timp[node] ) {
while( stiva.top() != vec ) {
components[nrComp].push_back( stiva.top() );
stiva.pop();
}
components[nrComp].push_back( stiva.top() );
stiva.pop();
components[nrComp].push_back( node );
nrComp++;
}
}
else if( vec != par )
low[node] = min( low[node], timp[vec] );
}
}
void solve() {
int n, m, i, j, x, y;
cin >> n >> m;
for( i = 0; i < m; i++ ) {
cin >> x >> y;
edges[x].push_back( y );
edges[y].push_back( x );
}
dfs( 1 );
cout << nrComp << "\n";
for( i = 0; i < nrComp; i++ ) {
for( auto x: components[i] )
cout << x << " ";
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio( false );
cin.tie( NULL );
cout.tie( NULL );
int t = 1;
//cin >> t;
while ( t-- )
solve();
return 0;
}