Pagini recente » Cod sursa (job #961743) | Cod sursa (job #130087) | Cod sursa (job #1014553) | Cod sursa (job #1922950) | Cod sursa (job #296129)
Cod sursa(job #296129)
#include <cstdio>
#include <vector>
using namespace std;
const int MAX_N = 100010;
const int nod_s = 1;
int n, m, z, k, sol;
int niv[MAX_N], f[MAX_N], par[MAX_N], c[MAX_N], scris[MAX_N], noduri[MAX_N];
int st1[MAX_N], st2[MAX_N];
vector <int> v[MAX_N];
int s[MAX_N][MAX_N];
void checkMin(int &a, int b)
{
if (a > b) a = b;
}
void df(int nod)
{
f[nod] = 1;
c[nod] = niv[nod];
for (int i = 0; i < v[nod].size(); ++i)
{
int fiu = v[nod][i];
if (!f[fiu])
{
par[fiu] = nod;
niv[fiu] = niv[nod] + 1;
st1[++k] = nod;
st2[k] = fiu;
df(fiu);
checkMin(c[nod], c[fiu]);
if (c[fiu] >= niv[nod])
{
++sol;
// printf("%d\n", sol);
while (!(st1[k] == nod && st2[k] == fiu))
{
s[sol][st1[k]] = 1;
s[sol][st2[k]] = 1;
--k;
}
s[sol][st1[k]] = s[sol][st2[k]] = 1;
--k;
}
}
else
if (par[nod] != fiu && niv[fiu] < niv[nod])
{
checkMin(c[nod], niv[fiu]);
st1[++k] = nod;
st2[k] = fiu;
}
}
}
int main()
{
int i, x, y;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
for (i = 1; i <= m; ++i)
{
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
niv[nod_s] = 1;
df(nod_s);
printf("%d\n", sol);
for (i = 1; i <= sol; ++i)
{
for (int j = 1; j <= n; ++j)
if (s[i][j] == 1) printf("%d ", j);
printf("\n");
}
}