Pagini recente » Cod sursa (job #653222) | Cod sursa (job #168243) | Cod sursa (job #404301) | Cod sursa (job #1740697) | Cod sursa (job #1227440)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
#include <utility>
#include <set>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define DIM 100009
using namespace std;
ofstream out("biconex.out");
int n , m , nr;
int dfn[DIM] , low[DIM];
vector < int > G[DIM];
typedef vector < int >::iterator IT;
set < int >C[DIM];
typedef set < int >::iterator JT;
stack < pair < int , int > >S;
void read();
void biconex( int x , int y );
void dfs( int , int , int );
void wrs();
int main()
{
read();
dfs(1,0,0);
wrs();
return 0;
}
void read()
{
ifstream in("biconex.in");
in >> n >> m;
for( int x , y ; m ; --m )
{
in >> x >> y;
G[x].pb(y);
G[y].pb(x);
}
for( int i=1 ; i<=n ; i++)
dfn[i] = -1;
}
void dfs( int start , int tata , int number )
{
dfn[start] = low[ start] = number;
for( IT i = G[start].begin() ; i!=G[start].end() ; ++i )
{
if( *i == tata )
continue;
if( dfn[*i] == - 1 )
{
S.push( mp ( start , *i ));
dfs(*i,start,number+1);
low[start] = min ( low[start] , low[*i] );
if( low[*i] >= dfn[start] )
biconex(start,*i);
}
else
low[start] = min ( low[start] , dfn[*i] );
}
}
void biconex( int x , int y )
{
++nr;
int ii , jj;
do
{
ii = S.top().f;
jj = S.top().s;
S.pop();
C[nr].insert(ii);
C[nr].insert(jj);
}
while( ii != x || jj != y );
}
void wrs()
{
out << nr << '\n';
for( int i = 1 ; i <= nr; ++i )
{
for( JT j = C[i].begin() ; j!=C[i].end(); ++j)
out << *j << " ";
out << '\n';
}
}