Pagini recente » Cod sursa (job #174610) | Cod sursa (job #1607318) | Cod sursa (job #211708) | Cod sursa (job #2318257) | Cod sursa (job #478560)
Cod sursa(job #478560)
#include<fstream>
#include<vector>
#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);
}
}
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;
for(int i=0; i<LA[u].size(); i++)
{
int 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 if( x!=tu ) // a mau fist vizitat => muchie inapoi
low[u] = min(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];
for(int j=0; i<v.size(); j++) g<< v[j] <<" ";
g<<"\n";
}
}
int main()
{
read();
solve();
f.close();
g.close();
return 0;
}