Pagini recente » Cod sursa (job #1260665) | Cod sursa (job #219804) | Cod sursa (job #2626533) | Cod sursa (job #1238313) | Cod sursa (job #3224216)
#include <bits/stdc++.h>
#define L 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector <int> G[L], bcc[L];
stack <int> st;
int lev[L], ru[L], bccCnt;
void add_bcc(int node, int targetSize) {
while ((int)st.size() > targetSize) {
bcc[bccCnt].push_back(st.top());
st.pop();
}
bcc[bccCnt++].push_back(node);
}
void dfs(int node) {
st.push(node);
ru[node] = lev[node];
for (auto it : G[node])
if (lev[it])
ru[node] = min(ru[node], lev[it]);
else {
int sz = st.size();
lev[it] = lev[node] + 1;
dfs(it);
ru[node] = min(ru[node], ru[it]);
if (ru[it] >= lev[node])
add_bcc(node, sz);
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
fin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
lev[1] = 1;
dfs(1);
fout << bccCnt << "\n";
for (int i = 0; i < bccCnt; i++) {
for (auto it : bcc[i])
fout << it << " ";
fout << "\n";
}
return 0;
}