Pagini recente » Diferente pentru implica-te/arhiva-educationala intre reviziile 101 si 223 | Cod sursa (job #3241874) | Cod sursa (job #3243643) | Cod sursa (job #3256225) | Cod sursa (job #257764)
Cod sursa(job #257764)
#include <iostream>
#include <fstream>
#include <sstream>
#include <list>
#include <stack>
#include <utility>
using namespace std;
#ifdef __ACASA__
#define MAX 2000
#else
#define MAX 100010
#endif
typedef pair<int,int> pii;
list<int> A[MAX];
stack<pii> S;
int U[MAX];
int H[MAX];
int N, M, nr;
ostringstream buffer(ostringstream::out);
void DF( int x, int h, int last ) {
U[x] = H[x] = h;
for ( list<int>::iterator i=A[x].begin(); i!=A[x].end(); ++i ) {
if ( *i == last ) continue;
bool ok = false;
if ( U[*i]==0 ) {
ok = true;
S.push( make_pair(x,*i) );
DF(*i, h+1, x);
H[x] = H[*i]<H[x] ? H[*i] : H[x];
} else
H[x] = U[*i]<H[x] ? U[*i] : H[x];
if ( H[*i] >= h && ok ) {
nr ++;
buffer << S.top().second;
while ( S.top().first!=x && S.top().second!=*i && !S.empty() ) {
buffer << " " << S.top().first;
S.pop();
}
buffer << " " << S.top().first;
S.pop();
buffer << "\n";
}
}
}
int main() {
// load
ifstream in("biconex.in");
in >> N >> M;
while ( M-- ) {
int x, y;
in >> x >> y;
A[x].push_back(y);
A[y].push_back(x);
}
for ( int i=1; i<=N; ++i )
if ( U[i] == 0 )
DF(i,1,0);
ofstream("biconex.out") << nr << "\n" << buffer.str();
return 0;
}