Pagini recente » Cod sursa (job #1339184) | Cod sursa (job #2719584) | Cod sursa (job #1923033) | Cod sursa (job #239495) | Cod sursa (job #2940095)
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 7;
int n;
int m;
vector<int> g[N];
int dep[N];
int mindep[N];
vector<vector<int>> all;
vector<pair<int, int>> stk;
void dfs(int a) {
mindep[a] = dep[a];
for (auto &b : g[a]) {
if (dep[b] == -1) {
dep[b] = 1 + dep[a];
stk.push_back({a, b});
dfs(b);
mindep[a] = min(mindep[a], mindep[b]);
if (mindep[b] >= dep[a]) {
vector<int> cur;
while (1) {
assert(!stk.empty());
auto it = stk.back();
cur.push_back(it.first);
cur.push_back(it.second);
stk.pop_back();
if (it == make_pair(a, b)) {
break;
}
}
sort(cur.begin(), cur.end());
cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
all.push_back(cur);
}
} else {
if (dep[b] < dep[a] - 1) {
mindep[a] = min(mindep[a], dep[b]);
}
}
}
}
int main() {
///ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
///freopen ("input.txt", "r", stdin);
freopen ("biconex.in", "r", stdin), freopen ("biconex.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
dep[i] = -1;
}
for (int i = 1; i <= n; i++) {
if (dep[i] == -1) {
dep[i] = 0;
dfs(i);
assert(stk.empty());
}
}
cout << (int) all.size() << "\n";
for (auto &v : all) {
for (auto &x : v) {
cout << x << " ";
}
cout << "\n";
}
return 0;
}