Pagini recente » Cod sursa (job #3342848) | Cod sursa (job #3347121) | Cod sursa (job #3304604) | Cod sursa (job #3309873) | Cod sursa (job #3320359)
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> v;
vector<vector<int>> bicomp;
vector<bool> checked;
vector<int> depth;
vector<int> low;
stack <int> q;
void dfs(int nod,int p,int root){
q.push(nod);
checked[nod] = 1;
low[nod] = depth[nod];
bool verified = false;
for(int i=0;i<v[nod].size();i++){
int newnod = v[nod][i];
if(p == newnod)
continue;
if(checked[newnod] == 1)
low[nod] = min(low[nod],depth[newnod]);
else{
depth[newnod] = depth[nod] + 1;
dfs(newnod,nod,root);
low[nod] = min(low[nod],low[newnod]);
if(low[newnod] >= depth[nod] and verified == false){
verified = true;
vector<int> comp;
while(q.size()){
int top = q.top();
comp.push_back(top);
if(top == nod)
break;
q.pop();
}
bicomp.push_back(comp);
}
}
}
if(root==nod and q.size()){
vector<int> comp;
while(q.size()){
int top = q.top();
q.pop();
comp.push_back(top);
if(top == nod)
break;
}
bicomp.push_back(comp);
}
}
int main(){
ifstream cin("biconex.in");
ofstream cout("biconex.out");
cin>>n>>m;
v.resize(n+1);
checked.resize(n+1,0);
depth.resize(n+1,0);
low.resize(n+1);
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,1,1);
cout<<bicomp.size()<<"\n";
for(int i = 0 ; i<bicomp.size(); i++){
for(int j = 0 ; j < bicomp[i].size(); j++)
cout<<bicomp[i][j]<<" ";
cout<<"\n";
}
}