Pagini recente » Cod sursa (job #1046165) | Cod sursa (job #2882894) | Cod sursa (job #3120577) | Cod sursa (job #1902483) | Cod sursa (job #2778868)
#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5 + 7;
int n, m, q, depInitial[N], minDepInitial[N];
vector<int> gInitial[N], kidsInitial[N], g[N];
vector<pair<int, int>> stk;
vector<vector<int>> comps;
void dfsInitial(int a) {
minDepInitial[a] = depInitial[a];
for (auto &b : gInitial[a]) {
if (depInitial[b] == 0) {
stk.push_back({a, b});
kidsInitial[a].push_back(b);
depInitial[b] = 1 + depInitial[a];
dfsInitial(b);
minDepInitial[a] = min(minDepInitial[a], minDepInitial[b]);
if (depInitial[a] <= minDepInitial[b]) {
vector<int> sol;
while (1) {
auto it = stk.back();
sol.push_back(it.first);
sol.push_back(it.second);
stk.pop_back();
if (it == make_pair(a, b)) break;
}
sort(sol.begin(), sol.end());
comps.push_back({});
for (int i = 0; i < (int) sol.size(); i++) {
if (i == 0 || (sol[i] != sol[i - 1])) {
comps.back().push_back(sol[i]);
}
}
}
} else {
if (depInitial[b] < depInitial[a] - 1) {
minDepInitial[a] = min(minDepInitial[a], depInitial[b]);
}
}
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int foo, bar;
cin >> foo >> bar;
gInitial[foo].push_back(bar);
swap(foo, bar);
gInitial[foo].push_back(bar);
}
depInitial[1] = 1;
dfsInitial(1);
cout << (int) comps.size() << "\n";
for (auto &c : comps) {
for (auto &x : c) {
cout << x << " ";
}
cout << "\n";
}
return 0;
}