Pagini recente » Cod sursa (job #1458665) | Cod sursa (job #2402475) | Cod sursa (job #2392030) | Cod sursa (job #1346373) | Cod sursa (job #2889836)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
// nma = nivel minim accesibil
int n, m, x, y, niv[100005], nma[100005], cB;
vector<int> G[100005], ans[100005];
bitset<100005> v;
stack<int> st;
void compBiconexe(int nod, int i) {
if(niv[nod] <= nma[i]) {
cB++;
do {
x = st.top();
st.pop();
ans[cB].push_back(x);
} while(x != i);
ans[cB].push_back(nod);
}
}
void dfs(int nod, int tata) {
v[nod] = true;
niv[nod] = niv[tata] + 1;
nma[nod] = niv[nod];
/// stiva pt componentele biconexe
st.push(nod);
int desc = 0;
for(auto i : G[nod]) {
if(i != tata) {
if(v[i]) {
nma[nod] = min(nma[nod], niv[i]);
} else {
desc++;
dfs(i, nod);
nma[nod] = min(nma[nod], nma[i]);
compBiconexe(nod, i);
}
}
}
}
int main() {
fin >> n >> m;
for(int i = 1; i <= m; i++) {
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
fin.close();
for(int i = 1; i <= n; i++) {
if(!v[i]) {
dfs(i, 0);
}
}
fout << cB << "\n";
for(int i = 1; i <= cB; i++) {
for(int it : ans[i]) {
fout << it << " ";
}
fout << "\n";
}
return 0;
}