Pagini recente » Cod sursa (job #1807157) | Cod sursa (job #812320) | Cod sursa (job #2314198) | Cod sursa (job #371565) | Cod sursa (job #2811683)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int N=1e5+1;
int n,m,t[N],t_min[N],timp,n_cbc;
vector <int> a[N];
vector <int> cbc[N];
stack<int> stiva;
void adauga_cbc(int x,int y)
{
n_cbc++;
while(stiva.top()!=y)
{
cbc[n_cbc].push_back(stiva.top());
stiva.pop();
}
cbc[n_cbc].push_back(y);
cbc[n_cbc].push_back(x);
stiva.pop();
/*vector <int> comp;
while(stiva.top().first!=e.first || stiva.top().second!=e.second)
{
comp.push_back(stiva.top().first);
comp.push_back(stiva.top().second);
stiva.pop();
}
comp.push_back(stiva.top().first);
comp.push_back(stiva.top().second);
stiva.pop();
sort(comp.begin(),comp.end());
n_cbc++;
cbc[n_cbc].push_back(comp[0]);
for(size_t i=1;i<comp.size();i++)
{
if(comp[i]!=comp[i-1])
{
cbc[n_cbc].push_back(comp[i]);
}
}*/
}
void dfs(int x,int tata)
{
t_min[x]=t[x]=++timp;
stiva.push(x);
for(auto y:a[x])
{
if(t[y]==0)
{
dfs(y,x);
t_min[x]=min(t_min[x],t_min[y]);
if(t_min[y]>=t[x])
{
//p_art.push_back(x); ///x este pct de articulatie
adauga_cbc(x,y);
}
}
else
if(y!=tata)
{
t_min[x]=min(t_min[x],t[y]);
}
}
/*if(tata==0 && nr_fii>1)
{
p_art.push_back(x); ///x este pct de articulatie
}*/
}
int main()
{
f>>n>>m;
for(int i=0;i<m;i++)
{
int x,y;
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
f.close();
for(int i=1;i<=n;i++)
{
if(t[i]==0)
{
dfs(i,0);
}
}
g<<n_cbc<<"\n";
for(int i=1;i<=n_cbc;i++)
{
for(auto x:cbc[i])
{
g<<x<<" ";
}
g<<"\n";
}
return 0;
}