Pagini recente » Cod sursa (job #2894176) | Cod sursa (job #990106) | Cod sursa (job #586658) | Cod sursa (job #1563096) | Cod sursa (job #558150)
Cod sursa(job #558150)
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;
#define N_MAX 100005
typedef pair <int,int> p;
set <int> bc[N_MAX];
int nrBc;
vector <int> a[N_MAX];
int n,m,i,j,x,y;
int NR=1;
int low[N_MAX],up[N_MAX];
int tata[N_MAX];
stack <p> ST;
void cBc(int x,int y)
{
int _X, _Y;
nrBc++;
do
{
_X = ST.top().first;
_Y = ST.top().second;
ST.pop();
bc[nrBc].insert(_X);
bc[nrBc].insert(_Y);
}while (_X != x || _Y != y);
}
void df(int nod)
{
low[nod]=NR;
up[nod]=NR;
NR++;
vector <int> ::iterator it;
for(it=a[nod].begin();it!=a[nod].end();it++)
{
if(low[*it]==0)
{
ST.push(p(nod,*it));
tata[*it]=nod;
df(*it);
low[nod]=min(low[nod],low[*it]);
if(up[nod]<=low[*it])
cBc(nod,*it);
}
else
{
if(tata[nod]!=*it)
low[nod]=min(low[nod],low[*it]);
}
}
}
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",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
df(1);
printf("%d\n",nrBc);
for(i=1;i<=nrBc;i++)
{
set <int> ::iterator it;
for(it=bc[i].begin();it!=bc[i].end();it++)
printf("%d ",*it);
printf("\n");
}
return 0;
}