Pagini recente » Cod sursa (job #616670) | Cod sursa (job #1007435) | Cod sursa (job #601282) | Monitorul de evaluare | Cod sursa (job #633397)
Cod sursa(job #633397)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define Nmax 100001
#define Mmax 200001
using namespace std;
int n,m,dfn[Nmax],low[Nmax],vf,nr;
vector<int> Sol[Nmax];
vector<int>::iterator it;
struct
{
int t,f;
}S[Mmax];
struct nod
{
int info;
nod *urm;
} *l[Nmax];
inline int min(int a,int b)
{
return a<b?a:b;
}
void add(nod *&p,int x)
{
nod *q=new nod;
q->info=x;
q->urm=p;
p=q;
}
void citire()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
int i,x,y;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(l[x],y);
add(l[y],x);
}
}
void init(int start)
{
int i;
for(i=1;i<=n;i++)
dfn[i]=low[i]=-1;
S[0].f=start;
S[0].t=-1;
vf=0;
}
void Conex(int x,int u)
{
int p,k;
nr++;
do
{
p=S[vf].f;
k=S[vf].t;
vf--;
Sol[nr].push_back(p);
Sol[nr].push_back(k);
}
while(p!=x || k!=u);
}
void dfs(int u,int tu,int niv)
{
//u vf curent, tu tatal lui u, niv nivelul curent
//dfn[x]=nr de ordine al vf x in parcurgerea DFS
//low[x]=nr de ordine al primului vf din parcurgerea DFS ce poate fi atins din x
//pe un alt lant decat lantul unic din arb partial DFS
dfn[u]=low[u]=niv;
int x;
nod *q;
for(q=l[u];q;q=q->urm)
{
x=q->info;
if(x!=tu) //x nu e tatal lui u
if(dfn[x]!=-1) // si nodul x e vizitat
low[u]=min(low[u],dfn[x]); //deci [u,x] m de intoarcere
else //nodul x e nevizitat
{
//pun in stiva muchia [u,x]
vf++;
S[vf].f=x;
S[vf].t=u;
dfs(x,u,niv+1);
low[u]=min(low[x],low[u]);
if(low[x]>=dfn[u])
Conex(x,u);
}
}
}
int main()
{
int i,c;
citire();
init(1);
dfs(1,-1,1);
printf("%d\n",nr);
for(i=1;i<=nr;i++)
{
c=0;
sort(Sol[i].begin(),Sol[i].end());
for(it=Sol[i].begin();it!=Sol[i].end();it++)
if(*it!=c)
{
printf("%d ",*it);
c=*it;
}
printf("\n");
}
return 0;
}