Pagini recente » Cod sursa (job #2695130) | Cod sursa (job #2038061) | Cod sursa (job #660991) | Cod sursa (job #524528) | Cod sursa (job #478562)
Cod sursa(job #478562)
#include<fstream>
#include<vector>
#include<algorithm>
#define inf "biconex.in"
#define outf "biconex.out"
#define NMax 100100
#define MMax 200100
using namespace std;
fstream f(inf,ios::in),g(outf,ios::out);
struct muchie { int t,f; } St[MMax]; int VfSt;
int N,M;
const int start = 1;
vector<int> LA[NMax];
vector< vector<int> > bc;
int nr,nrc,nrf;
int dfn[NMax],low[NMax],art[NMax];
void read()
{
int a,b;
f>>N>>M;
for(int i=1; i<=M; i++)
{
f>>a>>b;
LA[a].push_back(b);
LA[b].push_back(a);
}
}
inline int min(int a,int b) { return ( a<b ? a : b ) ; }
void cache_bc(int x,int u)
{
vector<int> v; muchie p;
nrc++;
do
{
p = St[VfSt--];
v.push_back(p.t); v.push_back(p.f);
}
while( p.t!=u || p.f!=x );
bc.push_back( v );
}
void biconex(int u,int tu)
{
dfn[u] = low[u] = ++nr;
int x,i;
for(i=0; i<LA[u].size(); i++)
{
x = LA[u][i];
if( x!=tu && dfn[x]<dfn[u] ) { St[++VfSt].t = u ; St[VfSt].f = x; }
if( dfn[x]==-1 ) //nu a mai fost vizitat
{
if( u==start ) nrf++;
biconex(x,u);
low[u] = min(low[u],low[x]);
if( low[x] >= dfn[u] )
{
if( u!=start ) art[u] = 1;
cache_bc(x,u);
}
}
else // a mai fost vizitat => muchie inapoi
{
if( x!=tu ) low[u] = dfn[x];
}
}
}
void solve()
{
//Init
for(int i=1; i<=N; i++) dfn[i] = low[i] = -1;
St[VfSt].f = start; St[VfSt].t = -1;
//Solve
biconex(start,-1);
if( nrf>1 ) art[start] = 1;
g<< nrc <<"\n";
for(int i=0; i<bc.size(); i++)
{
vector<int> v = bc[i];
sort( v.begin(), v.end() );
for(int j=0; j<bc[i].size(); j++)
if( j!=0 && v[j]!=v[j-1] ) g<< v[j] <<" ";
else if( !j ) g<< v[j] <<" ";
g<<"\n";
}
}
int main()
{
read();
solve();
f.close();
g.close();
return 0;
}