Pagini recente » Cod sursa (job #3005222) | Cod sursa (job #869059) | Cod sursa (job #1552308) | Cod sursa (job #56245) | Cod sursa (job #1125151)
#include<cstdio>
#include<set>
#include<stack>
#include<vector>
#define NMax 100005
using namespace std;
int crt,comp=0,N,M,dfn[NMax],low[NMax];
set<int> bic[NMax];
stack<pair<int,int> > S;
vector<int> vc[NMax];
void comp_bicon (int x, int y)
{
comp++;
while (S.top().first!=x || S.top().second!=y)
{
bic[comp].insert(S.top().first);
bic[comp].insert(S.top().second);
S.pop();
}
bic[comp].insert(S.top().first);
bic[comp].insert(S.top().second);
S.pop();
}
void biconex (int prec, int nod)
{
int i,fiu;
dfn[nod]=low[nod]=++crt;
for (i=0; i<vc[nod].size(); i++)
{
fiu=vc[nod][i];
if (fiu!=prec && dfn[fiu]<dfn[nod])
S.push(make_pair(nod,fiu));
if (dfn[fiu]==-1)
{
biconex(nod,fiu);
low[nod]=min(low[nod],low[fiu]);
if (low[fiu]>=dfn[nod])
comp_bicon(nod,fiu);
}
else if (fiu!=prec)
low[nod]=min(low[nod],dfn[fiu]);
}
}
int main ()
{
int i,x,y;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=1; i<=M; i++)
{
scanf("%d%d",&x,&y);
vc[x].push_back(y);
vc[y].push_back(x);
}
for (i=1; i<=N; i++)
dfn[i]=low[i]=-1;
S.push(make_pair(-1,1));
biconex(-1,1);
printf("%d\n",comp);
for (i=1; i<=comp; i++, printf("\n"))
for (set<int>::iterator it=bic[i].begin(); it!=bic[i].end(); ++it)
printf("%d ",*it);
return 0;
}