Pagini recente » Cod sursa (job #13285) | Paginatie | Cod sursa (job #2784818) | Cod sursa (job #3193971) | Cod sursa (job #284339)
Cod sursa(job #284339)
#include <cstdio>
#include <string>
#include <stack>
#include <list>
#include <algorithm>
#define dim 100100
using namespace std;
struct nod
{
int nr;
nod *urm;
};
int n, m, fol[dim], nivel[dim], ct=0;
nod *prim[dim];
stack< pair<int, int> > s;
list<int> l[dim];
void add(nod *&p, int nr)
{
nod *n1=new nod;
n1->nr=nr;
n1->urm=p;
p=n1;
}
void el_st(int x1, int x2)
{
int nd1, nd2;
do
{
nd1=s.top().first;
nd2=s.top().second;
s.pop();
l[ct].push_back(nd1);
l[ct].push_back(nd2);
} while ((nd1!=x1 || nd2!=x2) && (nd1!=x2 || nd2!=x1));
ct++;
}
void dfs(int x, int par, int niv, int &niv_min)
{
if (fol[x]) niv_min=nivel[x];
else
{
int aux;
nod *cur;
fol[x]=1;
nivel[x]=niv;
niv_min=niv;
cur=prim[x];
while (cur)
{
if (cur->nr!=par)
{
if (nivel[cur->nr]<nivel[x])
{
s.push(make_pair(x, cur->nr));
dfs(cur->nr, x, niv+1, aux);
if (aux<niv_min) niv_min=aux;
if (aux>=niv) el_st(x, cur->nr);
}
}
cur=cur->urm;
}
}
}
int main()
{
int i, a, b;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d\n", &n, &m);
for (i=1; i<=m; i++)
{
scanf("%d %d\n", &a, &b);
add(prim[a], b);
add(prim[b], a);
}
dfs(1, -1, 1, a);
printf("%d\n", ct);
for (i=0; i<ct; i++)
{
memset(fol, 0, (n+1)*sizeof(int));
for (list<int>::iterator it=l[i].begin(); it!=l[i].end(); it++)
if (!fol[*it])
printf("%d ", *it), fol[*it]=1;
printf("\n");
}
return 0;
}