Pagini recente » Cod sursa (job #322071) | Cod sursa (job #1030723) | Cod sursa (job #859778) | Cod sursa (job #1050993) | Cod sursa (job #2847873)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int desc[100001];
int low[100001];
bool vis[100001];
vector < int > Ad[100001];
vector < int > biconex[100001];
int nrc;
stack < int > S;
void DFS( int nod, int parent ){
S.push( nod );
desc[nod] = desc[parent] + 1;
low[nod] = desc[nod];
vis[nod] = 1;
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
if( vis[w] == 0 ){
DFS(w, nod);
low[nod] = min( low[nod], low[w] );
if( low[w] >= desc[nod] && w != parent ){
nrc++;
S.push( nod );
while( !S.empty() && S.top() != w ){
biconex[nrc].push_back( S.top() );
S.pop();
}
if( !S.empty() ){
biconex[nrc].push_back( S.top() );
S.pop();
}
}
}
else if( w != parent ){
low[nod] = min( low[nod], desc[w]);
}
}
}
int main()
{
int N, M;
cin >> N >> M;
int x, y;
for( int i = 1; i <= M; ++i ){
cin >> x >> y;
Ad[x].push_back( y );
Ad[y].push_back( x );
}
DFS( 1, 0 );
cout << nrc << '\n';
for( int i = 1; i <= nrc; ++i ){
for( int j = 0; j < biconex[i].size(); ++j )
cout << biconex[i][j] << ' ';
cout << '\n';
}
}