Pagini recente » Cod sursa (job #3333364) | Cod sursa (job #3350783) | Cod sursa (job #3242397) | Cod sursa (job #1536417) | Cod sursa (job #3311347)
#include <fstream>
#include <vector>
#include <stack>
#define nmax (int)(1e5+1)
#define inf 1e9
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n,m,x,y,niv[nmax],minlv[nmax],total;
bool viz[nmax],pct[nmax];
vector<int>v[nmax],aux;
vector<pair<int,int>>punte;
vector<vector<int>>c;
stack<int>s;
void dfs(int nod,int t){
niv[nod]=minlv[nod]=niv[t]+1;
viz[nod]=1;
s.push(nod);
int fii=0;
for(auto i:v[nod])
if(!viz[i]){
fii++;
dfs(i,nod);
minlv[nod]=min(minlv[nod],minlv[i]);
if(minlv[i]>=niv[nod]){
if(!pct[nod]&&nod!=1){
total++;
pct[nod]=1;
}
if(minlv[i]>niv[nod])
punte.push_back({nod,i});
aux.clear();
while(!s.empty()&&s.top()!=i){
aux.push_back(s.top());
s.pop();
}
aux.push_back(i);
aux.push_back(nod);
s.pop();
c.push_back(aux);
}
}else if(i!=t)
minlv[nod]=min(minlv[nod],niv[i]);
if(nod==1&&fii>1){
pct[1]=1;
total++;
}
}
int main()
{
int task=1;
//cin>>task;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
if(task==1){
cout<<c.size()<<'\n';
for(auto i:c){
for(auto j:i)
cout<<j<<" ";
cout<<'\n';
}
}else if(task==2){
cout<<total<<'\n';
for(int i=1;i<=n;i++)
if(pct[i])
cout<<i<<" ";
}else{
cout<<punte.size()<<" ";
for(auto i:punte)
cout<<i.first<<" "<<i.second<<'\n';
}
return 0;
}