Pagini recente » Cod sursa (job #703590) | Cod sursa (job #1728027) | Cod sursa (job #1554263) | Cod sursa (job #2179979) | Cod sursa (job #937720)
Cod sursa(job #937720)
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define FORIT( it,v ) for( typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it )
const int max_n=100005;
vector<int> Vertex[max_n], Comp[max_n];
int n, m, a, b, i;
int nrComp;
int Deep[max_n], Low[max_n];
stack<int> Stack;
void get_min( int &a, int b ){
if( a>b )
a=b;
}
void df( int nod, int deep ){
if( Deep[nod] )
return ;
Deep[nod]=deep;
Low[nod]=deep;
Stack.push(nod);
FORIT( it, Vertex[nod] ){
if( !Deep[*it] ){
df( *it, deep+1 );
get_min( Low[nod], Low[*it] );
if( Low[*it] == deep ){
bool ok=1;
nrComp++;
Comp[nrComp].push_back(nod);
while( ok ){
Comp[nrComp].push_back( Stack.top () );
if( Stack.top() == *it )
ok=0;
Stack.pop();
}
}
}
get_min( Low[nod], Deep[*it] );
}
return ;
}
int main(){
assert(freopen("biconex.in","r",stdin));
assert(freopen("biconex.out","w",stdout));
scanf("%d %d", &n, &m);
for( ; m--; ){
scanf("%d %d", &a, &b );
Vertex[a].push_back( b );
Vertex[b].push_back( a );
}
df( 1,1 );
printf("%d\n",nrComp);
for( i=1; i<=nrComp; ++i, printf("\n") ){
sort( Comp[i].begin(), Comp[i].end() );
FORIT( it, Comp[i] )
printf("%d ", *it );
}
return 0;
}