Pagini recente » Cod sursa (job #2176471) | Clasament oni2015day1 | Cod sursa (job #2866448) | Cod sursa (job #457436) | Cod sursa (job #1999269)
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#define nmax 100005
#include <stack>
using namespace std;
vector <unsigned int> a[nmax];
vector <unsigned int> v[nmax];
unsigned int ll[nmax],niv[nmax],t[nmax];
stack < pair<unsigned int,unsigned int> > st;
bool viz[nmax];
unsigned int cost[nmax],n,k,nrm=INT_MAX,nr;
void tar(unsigned int x)
{
ll[x]=niv[x]=niv[t[x]]+1;
viz[x]=1;
unsigned int i,y;
pair<unsigned int,unsigned int> e;
for (i=0;i<a[x].size();i++)
{
y=a[x][i];
if (y!=t[x])
{
if (!niv[y])
{
t[y]=x;
st.push(make_pair(x,y));
tar(y);
ll[x]=min(ll[x],ll[y]);
if (ll[y]>=niv[x])
{
nr++;
do
{
e=st.top();
v[nr].push_back(e.second);
st.pop();
}
while (e.first!=x);
v[nr].push_back(e.first);
}
}
else
{
if (viz[y])
ll[x]=min(ll[x],niv[y]);
}
}
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
unsigned int m,i,x,y,j;
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
tar(1);
g<<nr<<'\n';
for (i=1;i<=nr;i++)
{
for (j=0;j<v[i].size();j++)
g<<v[i][j]<<' ';
g<<'\n';
}
f.close();
g.close();
return 0;
}