Pagini recente » Cod sursa (job #3163512) | Cod sursa (job #2533213) | Cod sursa (job #1440103) | Cod sursa (job #600282) | Cod sursa (job #2576508)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int MAXN = 1e5;
const int MAXM = 2e5;
int n, m;
vector<int> g[MAXN + 1];
int lvl[MAXN + 1], minn[MAXN + 1];
vector<int> bico[MAXN + 1];
int cnt;
stack<pair<int, int> > edges;
void dfs(int nod, int boss) {
lvl[nod] = minn[nod] = lvl[boss] + 1;
for (auto &x : g[nod]) {
if (x == boss) continue;
if (lvl[x]) minn[nod] = min(minn[nod], lvl[x]);
else {
edges.push({nod, x});
dfs(x, nod);
if (minn[x] >= lvl[nod]) {
++ cnt;
pair<int, int> cur;
do {
cur = edges.top();
edges.pop();
bico[cnt].push_back(cur.first);
bico[cnt].push_back(cur.second);
} while ((cur.first != x || cur.second != nod) && (cur.first != nod || cur.second != x));
sort(bico[cnt].begin(), bico[cnt].end());
bico[cnt].erase(unique(bico[cnt].begin(), bico[cnt].end()), bico[cnt].end());
}
minn[nod] = min(minn[nod], minn[x]);
}
}
}
int main() {
in >> n >> m;
for (int i = 1; i <= m; ++ i) {
int a, b;
in >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; ++ i) {
if (!lvl[i])
dfs(i, 0);
}
out << cnt << '\n';
for (int i = 1; i <= cnt; ++ i) {
for (auto x : bico[i])
out << x << ' ';
out << '\n';
}
return 0;
}