Pagini recente » Cod sursa (job #1111476) | Cod sursa (job #2349485) | Cod sursa (job #773415) | Cod sursa (job #2629851) | Cod sursa (job #1252282)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int N = 100002;
struct Edge {
int x, y;
bool operator != (const Edge &other) {
return (!(x == other.x && y == other.y));
}
};
int n, m, biconexe, dp [N], level [N], f [N], a [N];
bool used [N];
vector <Edge> ans [N];
vector <int> graph [N];
stack <Edge> st;
void dfs (int x) {
vector <int> :: iterator it;
Edge temp;
used [x] = 1;
dp [x] = level [x];
for (it = graph [x].begin (); it != graph [x].end (); ++ it)
if (*it != f [x]) {
temp.x = x;
temp.y = *it;
if (!used [*it]) {
st.push (temp);
level [*it] = level [x] + 1;
f [*it] = x;
dfs (*it);
dp [x] = min (dp [x], dp [*it]);
if (dp [*it] >= level [x]) {
++ biconexe;
while (st.top () != temp) {
ans [biconexe].push_back (st.top ());
st.pop ();
}
ans [biconexe].push_back (st.top ());
st.pop ();
}
}
else {
if (level [*it] < level [x]) {
dp [x] = min (dp [x], level [*it]);
st.push (temp);
}
}
}
}
int main () {
int i, x, y;
vector <Edge> :: iterator it;
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);
graph [x].push_back (y);
graph [y].push_back (x);
}
biconexe = 0;
for (i = 1; i <= n; i ++)
if (!used [i])
dfs (i);
printf ("%d\n", biconexe);
for (i = 1; i <= biconexe; i ++) {
for (it = ans [i].begin (); it != ans [i].end (); ++ it) {
a [(*it).x] = i;
a [(*it).y] = i;
}
for (it = ans [i].begin (); it != ans [i].end (); ++ it) {
if (a [(*it).x] == i) {
printf ("%d ", (*it).x);
a [(*it).x] = 0;
}
if (a [(*it).y] == i) {
printf ("%d ", (*it).y);
a [(*it).y] = 0;
}
}
printf ("\n");
}
return 0;
}