Pagini recente » Cod sursa (job #154037) | Cod sursa (job #2492893) | Cod sursa (job #13066) | Cod sursa (job #2419989) | Cod sursa (job #383608)
Cod sursa(job #383608)
#include<cstdio>
#include<vector>
using namespace std;
#define pb push_back
#define N 100001
#define minn(a,b) ((a<b)? (a):(b))
vector <int> a[N];
int n,m,dep[N],low[N],x,y,st[N][2],rez[100][100],num;
bool viz[N],critic[N];
void citire()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1; i<=m; ++i)
{
scanf("%d%d",&x,&y);
a[x].pb(y);
a[y].pb(x);
}
}
void dfs(int n)
{
viz[n]=true;
low[n]=dep[n];
size_t g=a[n].size();
for (size_t i=0; i<g; ++i)
{
if (!viz[a[n][i]])
{
dep[a[n][i]]=1+dep[n];
st[++st[0][0]][0]=n;
st[st[0][0]][1]=a[n][i];
dfs(a[n][i]);
low[n]=minn(low[a[n][i]],low[n]);
}
else
low[n]=minn(low[n],dep[a[n][i]]);
}
}
void afis()
{
printf("%d\n",num);
for (int i=num-1; i>=0; --i)
{
for (int j=rez[i][0]; j; --j)
printf("%d ",rez[i][j]);
printf("\n");
}
/*for (int i=1; i<=n; ++i)
printf("%d %d\n",dep[i],low[i]);*/
}
void noduri_critice()
{
for (int i=1; i<=n; ++i)
{
size_t g=a[i].size();
for (size_t j=0; j<g; ++j)
{
if (dep[i]<=low[a[i][j]])
{
critic[i]=true;
break;
}
}
}
}
void noduri()
{
noduri_critice();
bool ok=true;
for (int i=st[0][0]; i;--i)
{
if (ok)
rez[num][++rez[num][0]]=st[i][1];
if (critic[st[i][0]])
{
rez[num][++rez[num][0]]=st[i][0];
++num;
ok=true;
}
else
{
rez[num][++rez[num][0]]=st[i][0];
ok=false;
}
}
}
int main()
{
citire();
dfs(1);
noduri();
afis();
return 0;
}