Pagini recente » Cod sursa (job #1409448) | Cod sursa (job #143026) | Cod sursa (job #2876235) | Cod sursa (job #2395652) | Cod sursa (job #395804)
Cod sursa(job #395804)
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#define N 100005
#define inf 0x3f3f3f3f
using namespace std;
vector<int> L[N],rez[N];
stack< pair<int, int> > S;
int jos[N],niv[N],tata[N];
int kont;
char E[N];
void dfs(int nod)
{
E[nod]=1;
int min=niv[nod];
for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); it++)
{
//daca e legat cu o muchie inversa de un predecesor diferit de tatal lui
if (E[*it] && tata[nod]!=*it && niv[*it]<min) min=niv[*it];
//daca nodul urmator nu a fost descoperit inca
if (!E[*it])
{
tata[*it]=nod; //devine tatal lui
niv[*it]=niv[nod]+1; //se incrementeaza nivelul
dfs(*it); //il analizeaza recursiv
if (jos[*it]<min) min=jos[*it]; //minimul dintre nivelurile minime accesibile
}
}
jos[nod]=min;
}
void biconex(int nod)
{
E[nod]=1;
for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); it++)
{
//daca e pe muchia de intoarcere
if (E[*it] && tata[nod]!=*it && niv[*it]<niv[nod])
S.push(make_pair(nod,*it));
//daca se afla pe un nod nou
if (!E[*it])
{
S.push(make_pair(nod,*it));
int nr=*it;
biconex(nr);
if (jos[*it]>=niv[nod])
{
kont++;
for (; S.top().first!=nod && S.top().second!=*it; S.pop())
rez[kont].push_back(S.top().first);
rez[kont].push_back(S.top().first);
if (rez[kont].size()==1) rez[kont].push_back(S.top().second);
S.pop();
}
}
}
}
int main()
{
int n,m;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
L[x].push_back(y);
L[y].push_back(x);
}
memset(E,0,sizeof(E));
memset(jos,inf,sizeof(jos));
jos[1]=1;
niv[1]=1;
dfs(1);
memset(E,0,sizeof(E));
biconex(1);
printf("%d\n",kont);
for (int i=1; i<=kont; i++, printf("\n"))
for (vector<int>::iterator it=rez[i].begin(); it!=rez[i].end(); it++)
printf("%d ",*it);
return 0;
}