Pagini recente » Cod sursa (job #1274835) | Cod sursa (job #945958) | Cod sursa (job #1756885) | Cod sursa (job #2125232) | Cod sursa (job #372889)
Cod sursa(job #372889)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define NM 100005
#define FOR(i,a,b)for(int i=(a);i<=(b);++i)
#define PB push_back
int N,M,L[NM],MU[NM][2],cate,LOW[NM],LOWN[NM],bicomp;
vector <int> G[NM],BI[NM];
char U[NM];
void parc(int nod,int fat)
{
L[nod]=L[fat]+1;
LOW[nod]=LOWN[nod]=L[nod];
U[nod]=1;
FOR(i,0,G[nod].size()-1)
{
int nnod=G[nod][i];
if(nnod==fat) continue;
if(!U[nnod])
{
++cate;
MU[cate][0]=nod;
MU[cate][1]=nnod;
parc(nnod,nod);
LOW[nod]=min(LOW[nod],LOWN[nnod]);
}
LOWN[nod]=min(LOWN[nod],L[nnod]);
}
if(LOW[nod]==L[nod])
{
//trebuie sa scoti din stiva
++bicomp;
while(MU[cate][1]!=nod)
{
BI[bicomp].PB(MU[cate][1]);
--cate;
}
BI[bicomp].PB(nod);
if(BI[bicomp].size()==1)
{
BI[bicomp].clear();
--bicomp;
}
}
}
int main()
{
int a,b;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&N,&M);
FOR(i,1,M)
{
scanf("%d %d",&a,&b);
G[a].PB(b);
G[b].PB(a);
}
L[0]=0;
++cate;
MU[1][0]=0;
FOR(i,1,N)
if(!U[i])
{
MU[1][1]=i;
parc(i,0);
}
printf("%d\n",bicomp);
FOR(i,1,bicomp)
{
FOR(j,0,BI[i].size()-1)
printf("%d ",BI[i][j]);
printf("\n");
}
return 0;
}