Pagini recente » Cod sursa (job #1889644) | Cod sursa (job #316569) | Cod sursa (job #2824224) | Cod sursa (job #1757706) | Cod sursa (job #2801609)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
stack<pair<int, int>> st;
vector<int> gr[N], ans[N];
int niv[N], nr_con;
int dfs(int nod, int tata) {
int niv_min = niv[nod];
for (auto vec : gr[nod]) {
if (vec == tata) continue;
if (niv[vec] > niv[nod]) continue;
st.push({nod, vec});
if (niv[vec] == 0) {
niv[vec] = 1 + niv[nod];
int niv_min_crt = dfs(vec, nod);
if (niv_min_crt >= niv[nod]) {
while (!st.empty() && st.top() != make_pair(nod, vec) && st.top() != make_pair(vec, nod)) {
ans[nr_con].push_back(st.top().first);
ans[nr_con].push_back(st.top().second);
st.pop();
}
ans[nr_con].push_back(nod);
ans[nr_con].push_back(vec);
if (!st.empty())
st.pop();
++nr_con;
}
niv_min = min(niv_min_crt, niv_min);
}
niv_min = min(niv_min, niv[vec]);
}
return niv_min;
}
int main() {
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m;
cin >> n >> m;
while (m--) {
int x, y;
cin >> x >> y;
gr[x].push_back(y);
gr[y].push_back(x);
}
cin.close();
for (int i = 1; i <= n; ++i)
if (niv[i] == 0) {
niv[i] = 1;
dfs(i, 0);
}
cout << nr_con << "\n";
for (int i = 0; i < nr_con; ++i) {
sort(ans[i].begin(), ans[i].end());
ans[i].resize(distance(ans[i].begin(), unique(ans[i].begin(), ans[i].end())));
for (auto j : ans[i])
cout << j << " ";
cout << "\n";
}
cout.close();
return 0;
}