Pagini recente » Cod sursa (job #1766659) | Cod sursa (job #499768) | Cod sursa (job #2627967) | Cod sursa (job #2115725) | Cod sursa (job #606512)
Cod sursa(job #606512)
# include <algorithm>
# include <cstdio>
# include <cstring>
# include <stack>
# include <vector>
using namespace std;
# define x first
# define y second
const char *FIN = "biconex.in", *FOU = "biconex.out";
const int MAX = 100005;
vector <int> G[MAX];
vector < vector <int> > C;
stack < pair <int, int> > stiva;
int N, M, df[MAX], back[MAX];
inline void getmin (int &a, int b) {
a = a < b ? a : b ;
}
inline void extrage (int x, int y) {
vector <int> aux;
for (pair <int, int> ex (-1, -1); ex.x != x || ex.y != y; aux.push_back (ex.x), aux.push_back (ex.y))
ex = stiva.top (), stiva.pop ();
C.push_back (aux);
}
void dfs (int N, int F, int cnt) {
df[N] = back[N] = cnt;
for (vector <int> :: iterator it = G[N].begin (); it != G[N].end (); ++it) {
if (*it != F) {
if (df[*it] == -1) {
stiva.push (make_pair (N, *it));
dfs (*it, N, cnt + 1);
getmin (back[N], back[*it]);
if (back[*it] >= df[N]) extrage (N, *it);
} else getmin (back[N], df[*it]);
}
}
}
int main (void) {
freopen (FIN, "r", stdin);
freopen (FOU, "w", stdout);
scanf ("%d %d", &N, &M);
for (int i = 1, x, y; i <= M; ++i) {
scanf ("%d %d", &x, &y);
G[x].push_back (y);
G[y].push_back (x);
}
memset (df, -1, sizeof (df));
dfs (1, 0, 0);
printf ("%u\n", C.size ());
for (size_t i = 0; i < C.size (); ++i, printf ("\n")) {
sort (C[i].begin (), C[i].end ());
C[i].resize (unique (C[i].begin (), C[i].end ()) - C[i].begin ());
for (size_t j = 0; j < C[i].size (); ++j)
printf ("%d ", C[i][j]);
}
}