Pagini recente » Cod sursa (job #430665) | Clasament concurs_freshmen | Cod sursa (job #1104599) | Cod sursa (job #3217326) | Cod sursa (job #428996)
Cod sursa(job #428996)
#include<stdio.h>
#include<stack>
#include<vector>
#define Nmax 100010
#define pb push_back
#define mp make_pair
using namespace std;
int niv[Nmax],low[Nmax],i,n,a,b,m,Cbcx,T[Nmax],bcx[Nmax];
vector<int> V[Nmax], Sol[Nmax];
stack < pair <int,int> > S;
void comp(int x, int y)
{
int a,b,i;
Cbcx++;
do
{
a=S.top().first;
b=S.top().second;
if(bcx[a]!=Cbcx) {Sol[Cbcx].pb(a); bcx[a]=Cbcx;}
if(bcx[b]!=Cbcx) {Sol[Cbcx].pb(b); bcx[b]=Cbcx;}
S.pop();
}
while(a!=x || b!=y);
}
void dfs (int nod, int nivel)
{
int i,N=V[nod].size(),fiu;
niv[nod]=low[nod]=nivel;
for(i=0;i<N;i++)
{
fiu=V[nod][i];
if(fiu==T[nod]) continue;
if(!niv[fiu])
{
T[fiu]=nod;
S.push(mp(nod,fiu));
dfs(fiu,nivel+1);
if(low[fiu]<low[nod]) low[nod]=low[fiu];
if(low[fiu]>=niv[nod]) comp(nod,fiu);
}
else if(low[fiu]<low[nod]) low[nod]=low[fiu];
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d",&a,&b);
V[a].pb(b);
V[b].pb(a);
}
dfs(1,1);
printf("%d\n",Cbcx);
for(a=1;a<=Cbcx;a++)
{
b=Sol[a].size();
for(i=0;i<b;i++)
printf("%d ",Sol[a][i]);
printf("\n");
}
return 0;
}