Pagini recente » Cod sursa (job #2255471) | Cod sursa (job #1415201) | Cod sursa (job #2707786) | Cod sursa (job #2920092) | Cod sursa (job #1665373)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
const int NMAX = 100005;
class BCCArticulationPoints {
private:
vector<int> st;
public:
int n, bcc;
vector<int> low;
vector<int> dft;
vector<vector<int>> v;
vector<vector<int>> comp;
vector<bool> art;
BCCArticulationPoints(int _n) {
bcc = 0;
n = _n;
low.resize(_n + 5);
dft.resize(_n + 5);
v.resize(_n + 5);
comp.resize(_n + 5);
art.resize(_n + 5);
}
void add_edge(int x, int y) {
v[x].pb(y);
v[y].pb(x);
}
void dfs(int x, int f) {
dft[x] = low[x] = dft[f] + 1;
for (auto it : v[x])
if (it != f) {
if (!dft[it]) {
st.pb(it);
dfs(it, x);
low[x] = min(low[x], low[it]);
if (low[it] >= dft[x]) { // x is an articulation point
bcc++;
art[x] = 1;
while (st.back() != it) {
comp[bcc].pb(st.back());
st.pop_back();
}
comp[bcc].pb(it);
st.pop_back();
comp[bcc].pb(x);
}
} else {
low[x] = min(low[x], dft[it]);
}
}
}
void find_BCC() {
st.clear();
dfs(1, 0);
}
};
BCCArticulationPoints g(NMAX);
int n, m;
int main() {
cin.sync_with_stdio(false);
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &n, &m);
for (; m; m--) {
int x, y;
scanf("%d%d", &x, &y);
g.add_edge(x, y);
}
g.find_BCC();
printf("%d\n", g.bcc);
for (int i = 1; i <= g.bcc; i++) {
for (auto it : g.comp[i])
printf("%d ", it);
printf("\n");
}
return 0;
}