Pagini recente » Cod sursa (job #1632228) | Cod sursa (job #279103) | Cod sursa (job #390907) | Cod sursa (job #307446) | Cod sursa (job #1257513)
#include <fstream>
#include <vector>
#include <stack>
#define mp make_pair
#define pb push_back
#define mare 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int>v[mare];
vector<pair<int,int> >q[mare],z;
vector<pair<int,int> > ::iterator it;
bool used[mare],ok[mare];
int x,y,m,n,niv[mare],l[mare],t[mare],rad,nr,i,a,b,lung,nrx=0;
inline void MemComp( int X, int Y )
{
vector< int > C;
pair< int, int > Mct, M1 = mp( X, Y ), M2 = mp( Y, X );
do
{
Mct = z.back();
q[nrx].pb(mp(Mct.first,Mct.second));
z.pop_back();
}
while( Mct != M1 && Mct != M2 );
}
void df(int x)
{vector <int>::iterator it;
used[x]=true;
l[x]=niv[x];
for (it=v[x].begin();it!=v[x].end();it++)
{if(*it!= t[x]&&niv[x]>niv[*it]) z.pb(mp(*it,x));
if(used[*it]==false)
{niv[*it]=niv[x]+1;
t[*it]=x;
df(*it);
if (l[x] > l[*it]) l[x] = l[*it];
if (l[*it] >= niv[x])
{nrx++;
MemComp( *it, x );
}
}
else if (*it!=t[x]&& l[x]> niv[*it]) l[x] = niv[*it];
}}
int main()
{f>>n>>m;
for (i=1;i<=m;i++)
{f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for (i=1;i<=n;i++)
if (!used[i])
{niv[i]=1;
rad=i;
nr=0;
df(i);
}
int j;
g<<nrx<<'\n';
for (i=1;i<=nrx;i++)
{for (j=1;j<=n;j++) ok[j]=false;
for (it=q[i].begin();it!=q[i].end();it++)
{if (!ok[(*it).first]) {g<<(*it).first<<" ";ok[(*it).first]=true;}
if (!ok[(*it).second]) {g<<(*it).second<<" ";ok[(*it).second]=true;}}
g<<'\n';
}
}