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