Pagini recente » Cod sursa (job #1684658) | Cod sursa (job #173914) | Cod sursa (job #1838403) | Cod sursa (job #290599) | Cod sursa (job #412421)
Cod sursa(job #412421)
#include <stdio.h>
#include <vector>
using namespace std;
const int Lg = 200010;
vector <int> Rez[Lg],Graf[Lg];
int low[Lg],niv[Lg],viz[Lg],st[Lg];
int n,m,nr,nr_rez,vf,a,b;
void citire()
{
scanf ("%d %d",&n,&m);
for (int i=0;i<m;i++)
{
scanf ("%d %d",&a,&b);
Graf[a].push_back(b);
Graf[b].push_back(a);
}
}
inline int min(int a,int b)
{
return a<b?a:b;
}
void add(int a,int b)
{
nr_rez++;
do
{
Rez[nr_rez].push_back(st[--vf]);
Rez[nr_rez].push_back(st[--vf]);
}while (st[vf+1]!=b || st[vf]!=a);
}
void df(int nod)
{
viz[nod]=1;
low[nod]=niv[nod]=nr++;
for (int i=0 ; i<Graf[nod].size() ; i++)
if (!viz[Graf[nod][i]])
{
st[vf++]=nod;
st[vf++]=Graf[nod][i];
df(Graf[nod][i]);
if (low[Graf[nod][i]]>=niv[nod])
add(nod,Graf[nod][i]);
low[nod]=min(low[nod],low[Graf[nod][i]]);
}
else
low[nod]=min(low[nod],niv[Graf[nod][i]]);
}
void solve()
{
for (int i=1;i<=n;i++)
if (!viz[i])
df(i);
printf("%d\n",nr_rez);
for (int i=1;i<=nr_rez;i++)
{
for (int j=0;j<Rez[i].size();j++)
viz[Rez[i][j]]=0;
for (int j=0;j<Rez[i].size();j++)
if (!viz[Rez[i][j]])
{
viz[Rez[i][j]]=1;
printf("%d ",Rez[i][j]);
}
printf("\n");
}
}
int main ()
{
freopen ("biconex.in","r",stdin);
freopen ("biconex.out","w",stdout);
citire();
solve();
return 0;
}