Pagini recente » Cod sursa (job #2052809) | Cod sursa (job #1082076) | Cod sursa (job #1648985) | Cod sursa (job #2839141) | Cod sursa (job #2002182)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
vector< pair<int,int> > v[nmax];
vector<int> l[2*nmax];
int st[2*nmax],x[2*nmax],y[2*nmax],lev[nmax],low[nmax],afis[nmax];
int n,m,u,comp,i,j;
void mark(int A)
{
int P=st[u];
u--;
if(P!=0)l[comp].push_back(x[P]);
if(P!=0)l[comp].push_back(y[P]);
if(P==A)
return;
mark(A);
}
void dfs(int x)
{
int nod=0;
for(int i=0;i<v[x].size();i++)
{
nod=v[x][i].first;
if(!lev[nod])
{
lev[nod]=lev[x]+1;
u++;st[u]=v[x][i].second;
dfs(nod);
if(low[nod]>=lev[x])
{
comp++;
mark(v[x][i].second);
}
if(low[nod]<low[x])
low[x]=low[nod];
}
else
{
low[x]=min(low[x],lev[nod]);
}
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
f>>n>>m;
for(i=1;i<=n;i++)
low[i]=(1<<30);
for(i=1;i<=m;i++)
{
f>>x[i]>>y[i];
v[x[i]].push_back({y[i],i});
v[y[i]].push_back({x[i],i});
}
lev[1]=1;
dfs(1);
mark(0);
g<<comp<<'\n';
for(i=1;i<=comp;i++)
{
for(j=0;j<l[i].size();j++)
{
if(!afis[l[i][j]])
g<<l[i][j]<<' ';
afis[l[i][j]]=1;
}
for(j=0;j<l[i].size();j++)
afis[l[i][j]]=0;
g<<'\n';
}
return 0;
}