Pagini recente » Arbori de intervale si aplicatii in geometria computationala | Rating Egor Orekhov (hazzle) | Cod sursa (job #692364) | Cod sursa (job #1314170) | Cod sursa (job #2413568)
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 10;
vector< int > gr[MAXN];
int lvl[MAXN], minn[MAXN];
stack< pair< int, int > > edges;
vector< int > bico[MAXN];
int cnt = 0;
void dfs(int node, int boss) {
lvl[node] = minn[node] = lvl[boss] + 1;
for(auto &x : gr[node]) {
if(x == boss) continue;
if(lvl[x]) minn[node] = min(minn[node], lvl[x]);
else {
edges.push({node, x});
dfs(x, node);
if(minn[x] >= lvl[node]) {
int a, b;
++cnt;
do {
tie(a, b) = edges.top();
edges.pop();
bico[cnt].emplace_back(a);
bico[cnt].emplace_back(b);
} while(a != node || b != x);
sort(all(bico[cnt]));
bico[cnt].erase(unique(all(bico[cnt])), bico[cnt].end());
}
minn[node] = min(minn[node], minn[x]);
}
}
}
int main() {
#ifdef BLAT
freopen("input", "r", stdin);
#else
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
srand(time(nullptr));
int n, m;
cin >> n >> m;
for(int i = 0, a, b; i < m; ++i) {
cin >> a >> b;
gr[a].emplace_back(b);
gr[b].emplace_back(a);
}
for(int i = 1; i <= n; ++i) {
if(!lvl[i]) dfs(i, 0);
}
cout << cnt << '\n';
for(int i = 1; i <= cnt; ++i) {
for(auto &x : bico[i]) cout << x << ' ';
cout << '\n';
}
return 0;
}