Pagini recente » Cod sursa (job #2675819) | Cod sursa (job #1575840) | Cod sursa (job #1429038) | Cod sursa (job #1309332) | Cod sursa (job #3347999)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=1e5+5;
const int MMAX=2e5+5;
int n, m;
vector<int> ad[NMAX];
vector<vector<int>> sol;
int nivel[NMAX], nma[NMAX];
stack<int> st;
void addCompBiconex(int x, int y){
vector<int> comp={x};
while(!st.empty()){
if(st.top()==x)
break;
comp.push_back(st.top());
st.pop();
}
sol.push_back(comp);
}
void dfs(int nod, int tata){
st.push(nod);
nivel[nod]=nivel[tata]+1;
nma[nod]=nivel[nod];
for(auto vecin: ad[nod]){
if(vecin==tata)
continue;
if(nivel[vecin]==0){
dfs(vecin, nod);
if(nma[vecin]>=nivel[nod]){
addCompBiconex(nod, vecin);
}
nma[nod]=min(nma[nod], nma[vecin]);
}else{
nma[nod]=min(nma[nod], nivel[vecin]);
}
}
}
int main()
{
fin>>n>>m;
int a, b;
for(int i=1;i<=m;i++){
fin>>a>>b;
ad[a].push_back(b);
ad[b].push_back(a);
}
dfs(1, 0);
fout<<sol.size()<<'\n';
for(auto comp: sol){
for(auto nod: comp)
fout<<nod<<" ";
fout<<'\n';
}
return 0;
}