Pagini recente » Cod sursa (job #1380734) | Cod sursa (job #667702) | Cod sursa (job #3226851) | Cod sursa (job #1144071) | Cod sursa (job #1386803)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define Nmax 100002
#define pb push_back
#define mp make_pair
FILE *f = fopen ( "biconex.in", "r" );
FILE *g = fopen ( "biconex.out", "w" );
vector < int > G[Nmax], Sol[Nmax];
stack < pair < int , int > > st;
int index = 1, idx[Nmax], lowlink[Nmax], nrs;
void AddComp ( int x ,int y ){
int ax, ay;
nrs++;
do{
ax = st.top().first;
ay = st.top().second;
st.pop();
Sol[nrs].pb ( ax );
Sol[nrs].pb ( ay );
}while( ax != x || ay != y );
}
void GetComp ( int nod, int pred ){
vector < int > :: iterator it;
idx[nod] = lowlink[nod] = index;
index++;
for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
if ( nod == pred ) continue;
if ( !idx[*it] ){
st.push ( mp ( nod, *it ) );
GetComp ( *it, nod );
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].pb ( y );
G[y].pb ( x );
}
for ( int i = 1; i <= N; ++i )
if ( !idx[i] )
GetComp ( i, 0 );
fprintf ( g, "%d\n", nrs );
for ( int i = 1; i <= nrs; ++i ){
sort ( Sol[i].begin(), Sol[i].end() );
Sol[i].erase ( unique ( Sol[i].begin(), Sol[i].end() ), Sol[i].end() );
for ( it = Sol[i].begin(); it < Sol[i].end(); ++ it )
fprintf ( g, "%d ", *it );
fprintf ( g, "\n" );
}
return 0;
}