Pagini recente » Cod sursa (job #1906826) | Cod sursa (job #514234) | Cod sursa (job #511249) | Cod sursa (job #1327476) | Cod sursa (job #2155744)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
struct Edge {int x, y; };
const int MAXN = 100005;
int n, m, t, ord[MAXN], low[MAXN], ncb;
bool viz[MAXN];
vector<int> g[MAXN];
vector<int> cb[MAXN];
stack<Edge> st;
void save_cb(int x) {
ncb++;
Edge e = st.top();
while (e.x != x) {
cb[ncb].push_back(e.y);
st.pop();
e = st.top();
}
cb[ncb].push_back(e.y);
cb[ncb].push_back(e.x);
st.pop();
}
void dfs(int x, int px) {
viz[x] = true;
ord[x] = ++t;
low[x] = ord[x];
for (int &y : g[x]) {
if (y == px) continue;
if (!viz[y]) {
st.push({x, y});
dfs(y, x);
low[x] = min(low[x], low[y]);
if (ord[x] <= low[y]) {
save_cb(x);
}
} else {
low[x] = min(low[x], ord[y]);
}
}
}
int main()
{
in >> n >> m;
for (int i = 1, x, y; i <= m; ++i) {
in >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
if (!viz[i]) {
dfs(i, -1);
}
}
out << ncb << "\n";
for (int i = 1; i <= ncb; ++i) {
sort(cb[i].begin(), cb[i].end(), less<int>());
for (int &y : cb[i]) out << y << " ";
out << "\n";
}
return 0;
}