Pagini recente » Rating Ganea Alexandra (azinganga_ale) | Utilizatori inregistrati la Summer Challenge 2007, Runda 1 | Cod sursa (job #3289501) | Cod sursa (job #2975682) | Cod sursa (job #485669)
Cod sursa(job #485669)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define forit(it, v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
const int MAX_N = 100001;
const int MAX_M = 200001;
int n, m, nr_sol, k;
int niv[MAX_N], str[MAX_N], p[MAX_N];
char f[MAX_N];
pair <int, int> stack[MAX_M];
vector <int> v[MAX_N], sol[MAX_N];
void df(int nod)
{
f[nod] = 1;
str[nod] = niv[nod];
forit(it, v[nod])
{
int fiu = *it;
if (!f[fiu])
{
niv[fiu] = niv[nod] + 1;
p[fiu] = nod;
stack[++k] = mp(nod, fiu);
df(fiu);
str[nod] = min(str[nod], str[fiu]);
if (str[fiu] >= niv[nod])
{
++nr_sol;
for (; stack[k] != mp(nod, fiu); --k)
{
sol[nr_sol].pb(stack[k].x);
sol[nr_sol].pb(stack[k].y);
}
sol[nr_sol].pb(nod);
sol[nr_sol].pb(fiu);
--k;
}
}
else if (p[nod] != fiu && niv[nod] > niv[fiu])
{
str[nod] = min(str[nod], niv[fiu]);
stack[++k] = mp(nod, fiu);
}
}
}
int main()
{
int i, j;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 1; i <= m; ++i)
{
int x, y;
scanf("%d %d", &x, &y);
v[x].pb(y);
v[y].pb(x);
}
niv[1] = 1;
df(1);
printf("%d\n", nr_sol);
for (i = 1; i <= nr_sol; ++i)
{
sort(sol[i].begin(), sol[i].end());
sol[i].pb(0);
for (j = 0; j < sol[i].size() - 1; ++j)
if (sol[i][j] != sol[i][j + 1])
printf("%d ", sol[i][j]);
printf("\n");
}
}