Pagini recente » Cod sursa (job #1774262) | Cod sursa (job #1895044) | Cod sursa (job #1442488) | Cod sursa (job #1176707) | Cod sursa (job #281509)
Cod sursa(job #281509)
#include <fstream>
#include <list>
#include <algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
#ifdef __ACASA__
#define MAX 100
#else
#define MAX 100100
#endif
typedef list<int> li;
typedef list< pair<int,int> > lii;
int Low[MAX], S[MAX];
int k, N, M;
li G[MAX];
list<li> Cache;
lii Stack;
void do_cache( int x, int y ) {
pair<int,int> thePair(x,y), tmpp;
li tmp;
while ( 1 ) {
bool ok = ( (tmpp=Stack.back()) == thePair ) ;
tmp.push_back( tmpp.first );
tmp.push_back( tmpp.second );
Stack.pop_back();
if ( ok ) break;
};
tmp.sort();
tmp.unique();
Cache.push_back( tmp );
}
void DF( int n, int lvl, int t ) {
Low[n] = lvl;
S[ ++k ] = n;
for ( li::iterator i=G[n].begin(); i!=G[n].end(); ++i ) {
if ( *i==t ) continue;
if ( Low[*i] == -1 ) {
Stack.push_back( make_pair(n,*i) );
DF( *i, lvl+1, n );
Low[n] = min(Low[n], Low[*i]);
if ( Low[*i] >= lvl )
do_cache(n,*i);
}
else
Low[n] = min(Low[n], Low[*i]);
}
}
int main() {
in >> N >> M;
while ( M-- ) {
int x,y;
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
memset( Low, 0xff, sizeof(Low) );
for ( int i=1; i<=N; ++i )
if ( Low[i] == -1 )
DF(i,0,0);
out << Cache.size() << "\n";
for ( list<li>::iterator II=Cache.begin(); II!=Cache.end(); ++II ) {
li tmp = *II;
for ( li::iterator i=tmp.begin(); i!=tmp.end(); ++i )
out << *i << " " ;
out << "\n";
}
return 0;
}