Pagini recente » Cod sursa (job #245538) | Cod sursa (job #2384958) | Cod sursa (job #2757444) | Cod sursa (job #1928838) | Cod sursa (job #2188863)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream in ("biconex.in");
ofstream out ("biconex.out");
const int NMAX = 1e5 + 5;
int m, n, k, nv;
int niv[NMAX], l[NMAX];
vector < int > g[NMAX];
stack < pair < int, int > > s;
set < int > comp[NMAX];
void get_data(int x, int y) {
int xs, ys;
do {
xs = s.top().first;
ys = s.top().second;
comp[k].insert (xs);
comp[k].insert (ys);
s.pop();
} while (xs != x || ys != y);
}
void dfs(int x, int par) {
l[x] = niv[x] = ++nv;
for (const int &y : g[x]) {
if (y == par)
continue;
if (!niv[y]) {
s.push ({x, y});
dfs (y, x);
l[x] = min(l[x], l[y]);
if (l[y] >= niv[x]) {
k++;
get_data(x, y);
}
} else
l[x] = min(l[x], niv[y]);
}
}
int main()
{
in >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
in >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs (1, 0);
out << k << '\n';
for (int i = 1; i <= k; ++i) {
for (const int &node : comp[i])
out << node << ' ';
out << '\n';
}
in.close();
out.close();
return 0;
}