Pagini recente » Diferente pentru problema/cbinteractiv intre reviziile 19 si 18 | Cod sursa (job #878385) | Cod sursa (job #929673) | Cod sursa (job #1521986) | Cod sursa (job #3348007)
#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()){
int vf=st.top();
comp.push_back(vf);
st.pop();
if(vf==y)
break;
}
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;
}