Pagini recente » Cod sursa (job #2424742) | Cod sursa (job #2938188) | Cod sursa (job #176419) | Cod sursa (job #1235652) | Cod sursa (job #1528388)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int NMAX=10005;
stack<int>stu;
stack<int>stv;
stack<int>st;
vector<int>G[NMAX];
vector<int>dfs_discover,dfs_low,articulation_vertex,dfs_parent;
int time,dfsRoot,rootChildren,n,nr;
void articulationPoint(int u)
{
int j,v;
++time;
dfs_discover[u]=dfs_low[u]=time;
for(j=0; j<G[u].size(); ++j)
{
v=G[u][j];
if(!dfs_discover[v])
{
stu.push(u);
stv.push(v);
dfs_parent[v]=u;
if(u==dfsRoot)
rootChildren++;
articulationPoint(v);
if(dfs_low[v]>=dfs_discover[u])
{
articulation_vertex[u]=true;
st.push(stv.top());
while(stu.top()!=u||stv.top()!=v)
{
st.push(stu.top());
stu.pop();
stv.pop();
}
st.push(stu.top());
st.push(0);
stu.pop();
stv.pop();
nr++;
}
dfs_low[u]=min(dfs_low[u],dfs_low[v]);
}
else
{
if(v!=dfs_parent[u])
dfs_low[u]=min(dfs_low[u],dfs_discover[v]);
}
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int n,m,i,x,y;
scanf("%d%d",&n,&m);
for(i=1; i<=m; ++i)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs_parent.assign(n+1,-1);
articulation_vertex.assign(n+1,0);
dfs_low.assign(n+1,0);
dfs_discover.assign(n+1,0);
for(i=1; i<=n; ++i)
{
if(!dfs_discover[i])
{
dfsRoot=i;
rootChildren=0;
articulationPoint(i);
articulation_vertex[dfsRoot]=(rootChildren>1);
}
}
printf("%d\n",nr);
st.pop();
while(st.size())
{
if(st.top())
printf("%d ",st.top());
else
printf("\n");
st.pop();
}
return 0;
}