Pagini recente » Cod sursa (job #3235461) | Cod sursa (job #703173) | Cod sursa (job #13908) | Cod sursa (job #2409752) | Cod sursa (job #1758063)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define Nmax 100002
ifstream fin( "biconex.in" );
ofstream fout( "biconex.out" );
int N, M, ind = 1, NrComp;
int Index[Nmax], LowLink[Nmax];
vector < int > G[Nmax], Comp[Nmax];
stack < pair < int, int > > St;
void GetComp( int nod1, int nod2 ){
NrComp++;
int x1, x2;
do{
x1 = St.top().first;
x2 = St.top().second;
St.pop();
Comp[NrComp].push_back(x1);
Comp[NrComp].push_back(x2);
}while( make_pair( nod1, nod2 ) != make_pair( x1, x2 ) );
}
void DFS( int nod ){
vector < int > :: iterator it;
Index[nod] = LowLink[nod] = ind++;
for( it = G[nod].begin(); it != G[nod].end(); ++it ){
if( !Index[*it] ){
St.push( make_pair( nod, *it ) );
DFS(*it);
LowLink[nod] = min( LowLink[nod], LowLink[*it] );
if( LowLink[*it] >= Index[nod] )
GetComp( nod, *it );
}
else
LowLink[nod] = min( LowLink[nod], Index[*it] );
}
}
int main(){
fin >> N >> M;
int x, y;
while( M-- ){
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for( int i = 1; i <= N; ++i )
if( !Index[i] )
DFS(i);
vector < int > :: iterator it;
fout << NrComp << "\n";
for( int i = 1; i <= NrComp; ++i ){
sort( Comp[i].begin(), Comp[i].end() );
Comp[i].erase( unique( Comp[i].begin(), Comp[i].end() ), Comp[i].end() );
for( it = Comp[i].begin(); it != Comp[i].end(); ++it )
fout << *it << " ";
fout << "\n";
}
return 0;
}