Pagini recente » Cod sursa (job #1057422) | Cod sursa (job #2822319) | Cod sursa (job #2047801) | Cod sursa (job #2971568) | Cod sursa (job #3226765)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100001
using namespace std;
ifstream fin( "biconex.in" );
ofstream fout( "biconex.out" );
int n, m, no_comp, timp;
vector <int> edges[NMAX];
int dfn[NMAX], low[NMAX], art[NMAX], viz[NMAX];
vector<int> cbc[NMAX];
stack <int> st;
void biconex( int node, int parent ) {
dfn[node] = low[node] = ++timp;
st.push( node );
for( unsigned int i = 0; i < edges[node].size(); i++ ) {
int newnode = edges[node][i];
if( dfn[newnode] == -1 ) {
biconex( newnode, node );
low[node] = min( low[node], low[newnode] );
// if( low[newnode] > dfn[node], at (newnode, node) e punte
if( low[newnode] >= dfn[node] ) {
art[node] = 1;
no_comp++;
cbc[no_comp].push_back( node );
while( !st.empty() && st.top() != newnode ) {
cbc[no_comp].push_back( st.top() );
st.pop();
}
if( !st.empty() && st.top() == newnode ) {
cbc[no_comp].push_back( st.top() );
st.pop();
}
}
}
else {
if( newnode != parent )
low[node] = min( low[node], dfn[newnode] );
}
}
}
int main() {
int x, y;
fin >> n >> m;
for( int i = 0; i < m; i++ ) {
fin >> x >> y;
edges[x].push_back( y );
edges[y].push_back( x );
}
for( int i = 0; i <= n; i++ )
dfn[i] = low[i] = -1;
biconex( 1, 0 );
fout << no_comp << '\n';
for( int i = 1; i <= no_comp; i++ ) {
for( unsigned int j = 0; j < cbc[i].size(); j++ )
fout << cbc[i][j] << ' ';
fout << '\n';
}
return 0;
}