Pagini recente » Cod sursa (job #524755) | Cod sursa (job #1897258) | Cod sursa (job #1163229) | Cod sursa (job #973707) | Cod sursa (job #1937216)
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 100005
#include <vector>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
vector < int > a[NMAX];
vector < pair < int, int > > st;
vector < vector < int > > sol;
int dist[NMAX], mdist[NMAX], n, m;
inline int min(const int & a, const int & b) {
if (a < b) return a;
return b;
}
void Comp(const int & x, const int & y) {
int a, b;
vector < int > v, w;
v.push_back(0);
do {
a = st.back().first;
b = st.back().second;
st.pop_back();
v.push_back(a);
v.push_back(b);
} while (a != x || b != y);
sort(v.begin(), v.end());
for (int i = 1; i < v.size(); i++)
if (v[i] != v[i - 1]) w.push_back(v[i]);
sol.push_back(w);
}
void DF (int nod, int father, int level) {
dist[nod] = mdist[nod] = level;
for (int i = 0; i < a[nod].size(); i++) {
if (a[nod][i] == father) continue;
int it = a[nod][i];
if (!dist[it]) {
st.push_back(make_pair(nod, it));
DF(it, nod, level + 1);
mdist[nod] = min(mdist[nod], mdist[it]);
if (mdist[it] >= dist[nod])
Comp(nod, it);
}
else mdist[nod] = min(mdist[nod], dist[it]);
}
}
int main()
{
f>>n>>m;
while (m--) {
int x, y;
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
DF(1, 0, 1);
g<<sol.size()<<'\n';
for (int i = 0; i < sol.size(); i++) {
for (int j = 0; j < sol[i].size(); j++)
g<<sol[i][j]<<' ';
g<<'\n';
}
return 0;
}