Pagini recente » Cod sursa (job #1187648) | Cod sursa (job #1127930) | Solutii preONI 2006 - Runda 1 | Cod sursa (job #208748) | Cod sursa (job #3292445)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,x,y,comp,nivel[100200],nma[100200];
vector <int> edges[100200],biconex[100200];
stack <int> st;
void dfs(int x,int t)
{
st.push(x);
nivel[x]=nma[x]=nivel[t]+1;
for(auto y:edges[x])
{
if(y!=t)
if(nivel[y]==0)
dfs(y,x), nma[x]=min(nma[x],nma[y]);
else
nma[x]=min(nma[x],nivel[y]);
}
if(nivel[t]<=nma[x] and t!=0)
{
comp++;
while(!st.empty() and st.top()!=x)
biconex[comp].push_back(st.top()), st.pop();
st.pop();
biconex[comp].push_back(x);
biconex[comp].push_back(t);
}
}
int main()
{
f>>n>>m;
for(int i=1; i<=m; i++)
f>>x>>y, edges[x].push_back(y), edges[y].push_back(x);
dfs(1,0);
g<<comp<<'\n';
for(int i=1; i<=comp; i++, g<<'\n')
for(auto it:biconex[i])
g<<it<<' ';
return 0;
}