Pagini recente » Cod sursa (job #1624952) | Cod sursa (job #688619) | Cod sursa (job #1907655) | Cod sursa (job #15201) | Cod sursa (job #1017142)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
const int NMAX = 100003;
vector <vector <int> > R;
vector <int> G[NMAX];
stack <int> S;
int node_depth[NMAX], min_depth[NMAX], s;
void DFS (const int &node, const int &depth) {
node_depth[node] = min_depth[node] = depth;
for (vector <int> :: iterator i = G[node].begin (); i != G[node].end (); ++i)
if (!node_depth[*i]) {
S.push (*i);
DFS (*i, depth + 1);
min_depth[node] = min (min_depth[node], min_depth[*i]);
if (node_depth[node] == min_depth[*i]) {
vector <int> N;
while (S.top () != *i)
N.push_back (S.top ()),
S.pop ();
S.pop ();
N.push_back (*i);
N.push_back (node);
R.push_back (N);
}
}
else
min_depth[node] = min (min_depth[node], node_depth[*i]);
}
int main () {
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
int N, M, a, b, i;
scanf ("%d%d", &N, &M);
for (i = 1; i <= M; ++i)
scanf ("%d%d", &a, &b),
G[a].push_back (b),
G[b].push_back (a);
for (i = 1; i <= N; ++i)
if (!node_depth[i])
DFS (i, 1);
printf ("%d", R.size ());
for (vector <vector <int> > :: iterator j = R.begin (); j != R.end (); ++j) {
printf ("\n");
for (vector <int> :: iterator k = j->begin (); k != j->end (); ++k)
printf ("%d ", *k);
}
}