Cod sursa(job #2174147)

Utilizator zhm248Mustatea Radu zhm248 Data 16 martie 2018 10:57:28
Problema Componente biconexe Scor 64
Compilator cpp Status done
Runda Arhiva educationala Marime 2.14 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int NMAX=100005;
stack<int>stu;
stack<int>stv;
stack<int>st;
vector<int>G[NMAX];
vector<int>dfs_discover,dfs_low,articulation_vertex,dfs_parent;
int timp,dfsRoot,rootChildren,n,nr;
void articulationPoint(int u)
{
    int j,v;
    ++timp;
    dfs_discover[u]=dfs_low[u]=timp;
    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;
}