Pagini recente » Cod sursa (job #2176132) | Cod sursa (job #45014) | Cod sursa (job #1722463) | Cod sursa (job #2526649) | Cod sursa (job #3186934)
#include <bits/stdc++.h>
using namespace std;
const int dim=1e5+5;
int n,m,dfn[dim],low[dim],timer,fii,art[dim],nr;
vector<int> G[dim];
vector<pair<int,int>> sol[dim];
stack<pair<int,int>> st;
void comp_biconexa(int u, int v){
nr++;
pair<int,int> muc;
do{
muc=st.top();
st.pop();
sol[nr].push_back(muc);
}while(!(muc.first==u and muc.second==v));
}
void biconex(int nod, int tata){
dfn[nod]=low[nod]=++timer;
for(auto x:G[nod]){
if(x!=tata and dfn[x]<dfn[nod]){
st.push({x,nod});
}
if(dfn[x]==-1){
if(nod==1){
fii++;
}
biconex(x,nod);
low[nod]=min(low[nod],low[x]);
if(low[x]>=dfn[nod]){
if(nod!=1){
art[nod]=1;
}
comp_biconexa(x,nod);
}
}
else{
if(x!=tata){
low[nod]=min(low[nod],dfn[x]);
}
}
}
}
int main(){
ifstream f("biconex.in");
ofstream g("biconex.out");
f>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=n;i++){
dfn[i]=low[i]=-1;
}
st.push({1,-1});
biconex(1,-1);
if(fii>=2){
art[1]=1;
}
// for(int i=1;i<=n;i++){
// if(art[i]){
// cout<<i<<' ';
// }
// }
g<<nr<<'\n';
for(int i=1;i<=nr;i++){
map<int,bool> fr;
for(auto x:sol[i]){
fr[x.first]=1;
fr[x.second]=1;
}
for(auto x:fr){
g<<x.first<<' ';
}
g<<'\n';
}
return 0;
}