Pagini recente » Cod sursa (job #2109957) | Cod sursa (job #1058714) | Monitorul de evaluare | Cod sursa (job #2004140) | Cod sursa (job #2815943)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int N=1e5+1;
int n,m,t[N],t_min[N],nrc,timp;
vector <int> a[N],cbc[N];
stack <int> stiva;
void adaugare_cbc(int x, int j){
++nrc;
while(stiva.top()!=j){
cbc[nrc].push_back(stiva.top());
stiva.pop();
}
cbc[nrc].push_back(j);
cbc[nrc].push_back(x);
stiva.pop();
}
void dfs(int x, int tata){
t[x]=t_min[x]=++timp;
stiva.push(x);
for(int j:a[x]){
if(!t[j]){
dfs(j,x);
t_min[x]=min(t_min[x],t_min[j]);
if(t_min[j]>=t[x]){
adaugare_cbc(x,j);
}
}else
if(j!=tata){
t_min[x]=min(t_min[x],t[j]);
}
}
}
int main() {
cin>>n>>m;
for(int i=1; i<=m; i++){
int x,y;
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
for(int i=1; i<=n; i++){
if(!t[i])
dfs(i,0);
}
cout<<nrc<<'\n';
for(int i=1; i<=nrc; i++){
for(int j:cbc[i])
cout<<j<<" ";
cout<<'\n';
}
return 0;
}