Pagini recente » Cod sursa (job #1677985) | Cod sursa (job #3277876) | Cod sursa (job #1699886) | Cod sursa (job #2946824) | Cod sursa (job #1032915)
#include<fstream>
#include<vector>
#include<set>
#include<stack>
#include<utility>
using namespace std;
#define max_n 100010
#define max_m 200010
ifstream f("biconex.in");
ofstream g("biconex.out");
int n , m , k;
vector< int > L[max_n];
stack< pair<int , int> >S;
set<int> Sol[max_m];
set<int>::iterator it;
bool Viz[max_n];
int Low[max_n];
void read(){
int nod_a , nod_b;
f>>n>>m;
for( int i = 1 ; i <= m ; i++ ){
f>>nod_a>>nod_b;
L[nod_a].push_back(nod_b);
L[nod_b].push_back(nod_a);
}
}
void dfs( int nod , int niv , int father ){
int next_nod;
Viz[nod] = true; Low[nod] = niv;
for( unsigned int i = 0 ; i < L[nod].size() ; i++ ){
next_nod = L[nod][i];
if( next_nod == father )
continue;
if( !Viz[next_nod] ){
S.push( make_pair(nod , next_nod) );
dfs( next_nod , niv + 1 , nod );
if( niv <= Low[next_nod] && S.size() ){
pair<int , int> p(nod , next_nod); k++;
while( p != S.top() ){
Sol[k].insert( S.top().first );
Sol[k].insert( S.top().second );
S.pop();
}
Sol[k].insert( S.top().first );
Sol[k].insert( S.top().second );
S.pop();
}
}
if( Low[next_nod] < Low[nod] )
Low[nod] = Low[next_nod];
}
}
void solve(){
for( int i = 1 ; i <= n ; i++ )
if( !Viz[i] )
dfs(i , 1 , 0);
}
void print(){
g<<k<<"\n";
for( int i = 1 ; i <= k ; i++ ){
for( it = Sol[i].begin() ; it != Sol[i].end() ; it++ )
g<<(*it)<<" ";
g<<"\n";
}
}
int main(){
read();
solve();
print();
return 0;
}