Pagini recente » Cod sursa (job #2555089) | Cod sursa (job #2842318) | Cod sursa (job #3267768) | Cod sursa (job #574196) | Cod sursa (job #488575)
Cod sursa(job #488575)
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <deque>
#include <fstream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef bool int01;
typedef char cha08;
typedef short int int16;
typedef int int32;
typedef float rea32;
typedef long long int int64;
typedef double rea64;
const cha08 Input[] = "biconex.in";
const cha08 Output[] = "biconex.out";
const int32 Dim = 100001;
int32 N, M;
int32 lvn[Dim], stn[Dim];
stack < pair <int32, int32> > s;
vector <int32> v[Dim];
vector < vector <int32> > comp;
void MakeBC( int32 x, int32 y ) {
int32 xx, yy;
vector <int32> aux;
do {
xx = s.top().first;
yy = s.top().second;
s.pop();
aux.push_back( xx );
aux.push_back( yy );
}
while( xx != x || yy != y );
comp.push_back( aux );
}
void DF( int32 nod, int32 tat, int32 lvl ) {
vector <int32> :: iterator it;
lvn[nod] = stn[nod] = lvl;
for( it = v[nod].begin(); it != v[nod].end(); ++it ) {
if( *it == tat )
continue;
if( lvn[*it] == -1 ) {
s.push( make_pair( nod, *it ) );
DF( *it, nod, lvl + 1 );
stn[nod] = min( stn[nod], stn[*it] );
if( stn[*it] >= lvn[nod] )
MakeBC( nod, *it );
}
else
stn[nod] = min( stn[nod], lvn[*it] );
}
}
int32 main() {
ifstream fin( Input );
ofstream fout( Output );
int32 i, j, x, y;
fin >> N >> M;
while( M-- ) {
fin >> x >> y;
v[x].push_back( y );
v[y].push_back( x );
}
memset( lvn, -1, sizeof( lvn ) );
DF( 1, 0, 0 );
fout << comp.size() << "\n";
for( i = 0; i < (int32) comp.size(); ++i ) {
sort( comp[i].begin(), comp[i].end() );
comp[i].erase( unique( comp[i].begin(), comp[i].end() ), comp[i].end() );
for( j = 0; j < (int32) comp[i].size(); ++j )
fout << comp[i][j] << " ";
fout << "\n";
}
fin.close();
fout.close();
return 0;
}