Pagini recente » Cod sursa (job #1905021) | Cod sursa (job #2321239) | Cod sursa (job #2240217) | Cod sursa (job #1893441) | Cod sursa (job #1412071)
#include <vector>
#include <fstream>
#include <set>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int N = 1e5 + 5;
set <int> comp[N];
vector <int> g[N];
stack <pair <int, int> > st;
int lo[N], niv[N], n, m, c;
void extract (int x, int y) {
int crtx, crty;
do {
crtx = st.top().first;
crty = st.top().second;
st.pop();
comp[c].insert(crtx);
comp[c].insert(crty);
} while (crtx != x || crty != y);
++c;
}
void dfs(int x, int tata, int lv) {
lo[x] = niv[x] = lv;
for (vector <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
if (*it == tata)
continue;
if (!niv[*it]) {
st.push(make_pair (x, *it));
dfs(*it, x, lv + 1);
lo[x] = min(lo[x], lo[*it]);
if (niv[x] <= lo[*it])
extract(x, *it);
}
else
lo[x] = min(lo[*it], niv[x]);
}
}
int main() {
fin >> n >> m;
for (int x, y; m; --m) {
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0, 1);
fout << c << "\n";
for (int i = 0; i < c; ++i) {
for (set <int> :: iterator it = comp[i].begin(); it != comp[i].end(); ++it)
fout << *it << " ";
fout << "\n";
}
}