Pagini recente » Istoria paginii runda/oni_2008 | Cod sursa (job #1120040) | Cod sursa (job #2889232) | Cod sursa (job #2372051) | Cod sursa (job #1438431)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <utility>
using namespace std;
#define Nmax 100002
FILE *f = fopen ( "biconex.in", "r" );
FILE *g = fopen ( "biconex.out", "w" );
vector < int > G[Nmax], Biconexe[Nmax];
stack < pair < int, int > > stiva;
int idx[Nmax], lowlink[Nmax], index = 1, nrBic;
void AddComp ( int x, int y ){
int ax, ay;
nrBic++;
do{
ax = stiva.top().first;
ay = stiva.top().second;
stiva.pop();
Biconexe[nrBic].push_back ( ax );
Biconexe[nrBic].push_back ( ay );
}while ( ax != x || ay != y );
}
void DFS ( int nod ){
vector < int > :: iterator it;
idx[nod] = lowlink[nod] = index++;
for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
if ( !idx[*it] ){
stiva.push ( make_pair ( nod, *it ) );
DFS ( *it );
lowlink[nod] = min ( lowlink[nod], lowlink[*it] );
if ( lowlink[*it] >= idx[nod] )
AddComp( nod, *it );
}
else
lowlink[nod] = min ( lowlink[nod], idx[*it] );
}
}
int main(){
int N, M, x, y;
vector < int > :: iterator it;
fscanf ( f, "%d%d", &N, &M );
for ( int i = 1; i <= M; ++i ){
fscanf ( f, "%d%d", &x, &y );
G[x].push_back ( y );
G[y].push_back ( x );
}
for ( int i = 1; i <= N; ++i )
if ( !idx[i] )
DFS ( i );
fprintf ( g, "%d\n", nrBic );
for ( int i = 1; i <= nrBic; ++i ){
sort ( Biconexe[i].begin(), Biconexe[i].end() );
Biconexe[i].erase ( unique ( Biconexe[i].begin(), Biconexe[i].end() ) , Biconexe[i].end() );
for ( it = Biconexe[i].begin(); it < Biconexe[i].end(); ++it )
fprintf ( g, "%d ", *it );
fprintf ( g, "\n" );
}
return 0;
}