Pagini recente » Cod sursa (job #804) | Cod sursa (job #3290294) | Profil andrici_cezar | Cod sursa (job #174895) | Cod sursa (job #559868)
Cod sursa(job #559868)
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
#define nmax 100005
#define mmax 200005
#define punct pair<int,int>
#define ff first
#define ss second
int n, nrsol;
stack<punct> st;
vector<int> G[nmax], solutii[nmax];
int lvl[nmax], c[nmax], viz[nmax];
void citire ()
{
int i, m, x, y;
freopen("biconex.in","r",stdin);
scanf("%d%d", &n, &m);
for (i = 1; i <= m; ++i)
{
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void add (int x, int y)
{
nrsol ++;
punct varf;
do{
varf = st.top (); st.pop ();
solutii[nrsol].push_back(varf.ss);
}while (varf.ff!=x && varf.ss!=y);
solutii[nrsol].push_back(varf.ff);
}
void dfs(int nod, int tata)
{
int i, urm;
viz[nod] = 1; lvl[nod] = lvl[tata] + 1; c[nod] = lvl[nod];
for (i = 0; i < G[nod].size (); ++i)
{
urm = G[nod][i];
if ( !viz[urm] )
{
st.push( make_pair(nod, urm) );
dfs(urm, nod);
if (c[urm] < c[nod]) c[nod] = c[urm];
if (c[urm] >= lvl[nod])
add(nod, urm);
}
else if (urm != tata && c[urm] < c[nod]) c[nod] = c[urm];
}
}
void afisare ()
{
int i, j;
freopen("biconex.out","w",stdout);
printf("%d\n", nrsol);
for (i = 1; i <= nrsol; ++i)
{
for (j = 0; j < solutii[i].size (); ++j)
printf("%d ", solutii[i][j]);
printf("\n");
}
}
int main ()
{
citire ();
dfs (1,0);
afisare ();
return 0;
}