Pagini recente » Cod sursa (job #2459411) | Cod sursa (job #840887) | Cod sursa (job #2246322) | Cod sursa (job #1112523) | Cod sursa (job #2264902)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
deque < int > m[100005];
stack <pair<int, int> >st;
vector< vector<int> > solutii;
int lvl[100005],low[100005];
bool viz[100005];
int nr;int nr_sol=0;
void comp_bic(int x, int y){
vector<int>sol;
int tx; int ty;
do{
tx=st.top().first;
ty=st.top().second;
st.pop();
sol.push_back(tx);
sol.push_back(ty);
}while(tx!=x or ty!=y);
sort(sol.begin(),sol.end());
sol.erase(unique(sol.begin(),sol.end()),sol.end());
nr_sol++;
solutii.push_back(sol);
}
void dfs(int node, int t){
viz[node]=1;
lvl[node]=lvl[t]+1;
low[node]=lvl[node];
for(int i=0;i<m[node].size();i++)
if(m[node][i]!=t){
if(viz[m[node][i]]==0){
if(node==1) nr++;
st.push(make_pair(node,m[node][i]));
dfs(m[node][i],node);
low[node]=min(low[node], low[m[node][i]]);
if(low[m[node][i]]>=lvl[node]){
comp_bic(node, m[node][i]);
}
}
else
low[node]=min(low[node],lvl[m[node][i]]);
}
}
int main()
{
int n,mu,i,a,b;
f>>n>>mu;
for(i=0;i<=n;i++)
low[i]=i;
for(i=1;i<=mu;i++){
f>>a>>b;
m[a].push_back(b);
m[b].push_back(a);
}
dfs(1,0);
// if(nr>1)
// g<<1<<"\n";
// for(i=1;i<=n;i++)
// g<<lvl[i]<<" ";
// g<<"\n";
// for(i=1;i<=n;i++)
// g<<low[i]<<" ";
g<<nr_sol<<"\n";
for(i=0;i<nr_sol;i++){
for(int j=0;j<solutii[i].size();j++)
g<<solutii[i][j]<<" ";
g<<"\n";
}
return 0;
}