Pagini recente » Cod sursa (job #3246659) | Cod sursa (job #209122) | Cod sursa (job #604351) | Cod sursa (job #1000920) | Cod sursa (job #2371154)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
const int mmax=200005;
vector< pair<int,int> > v[nmax];
vector<int> l[mmax];
int lev[nmax],low[nmax],ap[nmax];
int st[mmax],a[mmax],b[mmax];
int n,m,i,j,u,bcc;
void mark(int P)
{
l[bcc].push_back(a[st[u]]);
l[bcc].push_back(b[st[u]]);
if(st[u]!=P) {u--;mark(P);}
else u--;
}
void dfs(int x)
{
int nod,et;
for(int i=0;i<v[x].size();i++)
{
nod=v[x][i].first;et=v[x][i].second;
if(!lev[nod])
{
st[++u]=et;
lev[nod]=lev[x]+1;
dfs(nod);
if(low[nod]>=lev[x])
{
bcc++;
mark(et);
}
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[i]>>b[i];
v[a[i]].push_back({b[i],i});
v[b[i]].push_back({a[i],i});
}
lev[1]=1;
for(i=1;i<=n;i++)
low[i]=(1<<30);
dfs(1);
g<<bcc<<'\n';
for(i=1;i<=bcc;i++)
{
for(j=0;j<l[i].size();j++)
{
if(!ap[l[i][j]])
ap[l[i][j]]=1,g<<l[i][j]<<' ';
}
for(j=0;j<l[i].size();j++)
ap[l[i][j]]=0;
g<<'\n';
}
return 0;
}