Pagini recente » Cod sursa (job #2818533) | Cod sursa (job #91060) | Cod sursa (job #312071) | Cod sursa (job #1743326) | Cod sursa (job #2371143)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
const int mmax=2*nmax;
vector< pair<int,int> > v[nmax];
vector<int> li[mmax];
int st[mmax],unu[mmax],doi[mmax];
int low[nmax],lev[nmax];
int n,m,bcc,i,j,u,a,b;
void mark(int et)
{
li[bcc].push_back(unu[st[u]]);
li[bcc].push_back(doi[st[u]]);
u--;
if(et!=st[u+1]) mark(et);
}
void dfs(int x)
{
int nod=0;
low[x]=n+1;
for(int i=0;i<v[x].size();i++)
{
nod=v[x][i].first;
if(!lev[nod])
{
lev[nod]=lev[x]+1;
st[++u]=v[x][i].second;
dfs(v[x][i].first);
if(low[nod]>=lev[x])
{
bcc++;
mark(v[x][i].second);
}
if(low[nod]<low[x])
low[x]=low[nod];
}
else
{
if(lev[nod]<low[x])
low[x]=lev[nod];
}
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>a>>b;
v[a].push_back({b,i});
v[b].push_back({a,i});
unu[i]=a,doi[i]=b;
}
for(int s=1;s<=n;s++)
if(!lev[s])
{
lev[s]=1;
dfs(s);
}
g<<bcc<<'\n';
for(i=1;i<=bcc;i++)
{
for(j=0;j<li[i].size();j++)
if(lev[li[i][j]])
g<<li[i][j]<<' ',lev[li[i][j]]=0;
for(j=0;j<li[i].size();j++)
lev[li[i][j]]=1;
g<<'\n';
}
return 0;
}