Pagini recente » Cod sursa (job #814280) | Cod sursa (job #64111) | Cod sursa (job #2487417) | Cod sursa (job #3195865) | Cod sursa (job #2811703)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m, T[100002], lvl[100002];
vector<vector<int>> adj, rez;
stack<pair<int, int>> st;
void dfs(int act, int prev, int nivel) {
T[act] = lvl[act] = nivel;
for (int i = 0; i < adj[act].size(); i++) {
int nxt = adj[act][i];
if (nxt == prev) {
continue;
}
else {
if (lvl[nxt] == -1) {
st.push({ act, nxt });
dfs(nxt, act, nivel + 1);
T[act] = min(T[act], T[nxt]);
if (T[nxt] >= lvl[act]) {
int tx, ty;
vector<int> inter;
do {
tx = st.top().first;
ty = st.top().second;
st.pop();
inter.emplace_back(tx);
inter.emplace_back(ty);
} while (tx != act || ty != nxt);
rez.emplace_back(inter);
}
}
else {
T[act] = min(T[act], lvl[nxt]);
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i <= n; i++) {
adj.emplace_back(vector<int>());
lvl[i] = -1;
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
adj[x].emplace_back(y);
adj[y].emplace_back(x);
}
dfs(1, 0, 1);
cout << rez.size() << '\n';
for (int i = 0; i < rez.size(); i++) {
sort(rez[i].begin(), rez[i].end());
cout << rez[i][0]<<' ';
for (int j = 1; j < rez[i].size(); j++) {
if (rez[i][j] != rez[i][j - 1]) {
cout << rez[i][j] << ' ';
}
}
cout << '\n';
}
}