Pagini recente » Cod sursa (job #1350312) | Cod sursa (job #2123852) | Cod sursa (job #606792) | Cod sursa (job #978192) | Cod sursa (job #296136)
Cod sursa(job #296136)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 100010;
const int nod_s = 1;
const int INF = 0x3f3f3f3f;
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], s[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].push_back(st1[k]);
s[sol].push_back(st2[k]);
--k;
}
s[sol].push_back(st1[k]);
s[sol].push_back(st2[k]);
--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)
{
sort(s[i].begin(), s[i].end());
s[i].push_back(INF);
for (int j = 0; j < s[i].size() - 1; ++j)
if (s[i][j] != s[i][j + 1]) printf("%d ", s[i][j]);
printf("\n");
}
}