Pagini recente » Cod sursa (job #517416) | Cod sursa (job #1840583) | Cod sursa (job #3260044) | Cod sursa (job #1832499) | Cod sursa (job #3320052)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
vector<int>niv;
vector<int>niv_min;
vector<int>G[100005];
stack<pair<int,int>>st;
int n,m;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<vector<int>> comps;
void dfs(int nod, vector<int>& viz){
viz[nod]=1;
niv_min[nod]=niv[nod];
for(auto y : G[nod]){
if(viz[y]==0){
st.push({nod,y});
niv[y]=niv[nod]+1;
dfs(y, viz);
if(niv[nod] <= niv_min[y]){
vector<int> comp;
pair<int,int> mc;
do{
mc=st.top();
st.pop();
comp.push_back(mc.second);
}while(mc.first!=nod || mc.second!=y );
comp.push_back(nod);
comps.push_back(comp);
}
niv_min[nod]=min(niv_min[nod], niv_min[y]);
}
else{
if(niv[y] < niv[nod]-1){
niv_min[nod]=min(niv_min[nod], niv[y]);
}
}
}
}
int main(){
vector<int>viz;
f>>n>>m;
viz.assign(n+1, 0);
niv.assign(n+1, 0);
niv_min.assign(n+1, 0);
for( int i=0;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++)
if(viz[i]==0)
dfs(i, viz);
g<<comps.size()<<"\n";
for(auto &comp:comps){
for(auto x:comp)
g<<x<<" ";
g<<"\n";
}
g.close();
f.close();
}