Cod sursa(job #2394067)

Utilizator AlexToveAlexandru Toader AlexTove Data 1 aprilie 2019 12:00:30
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <vector>
#include <stack>
#include <fstream>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

vector <int> g[100005];
vector <int> dfs_discover,dfs_low,articulation_vertex,dfs_parent;
vector<int> sol[100005];
stack< pair<int, int> >st;
int cc;

int time,dfsroot,rootchildren,n;

void golire(int u, int v)
{
    int i, j;
    sol[cc].push_back(st.top().second);
    do
    {
        i = st.top().first;
        j = st.top().second;
        sol[cc].push_back(i);
        //fout<<i<<" "<<j<<'\n';
        st.pop();
    }while(i!=u && j!=v);
    //fout<<'\n';
}

void articulationpoint(int u)
{
    int v,j;
    time++;
    dfs_discover[u]=time;
    dfs_low[u]=time;
    for(j=0;j<g[u].size();j++)
    {
        v=g[u][j];
        if(!dfs_discover[v])
        {
            st.push({u, v});
            dfs_parent[v]=u;
            if(u==dfsroot)
                rootchildren++;
            articulationpoint(v);
            if(dfs_low[v]>=dfs_discover[u])
            {
                articulation_vertex[u]=1;
                cc++;
                golire(u, v);
            }
            dfs_low[u]=min(dfs_low[u],dfs_low[v]);
        }
        else
            if(dfs_parent[u]!=v)
                dfs_low[u]=min(dfs_low[u],dfs_discover[v]);
    }
}

int main()
{
    int m,u,v,i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs_parent.assign(n+1,0);
    dfs_low.assign(n+1,0);
    dfs_discover.assign(n+1,0);
    articulation_vertex.assign(n+1,0);
    for(i=1;i<=n;i++)
        if(dfs_discover[i]==0)
        {
            dfsroot=i;
            rootchildren=0;
            articulationpoint(i);
            articulation_vertex[dfsroot]=rootchildren>1;
        }
    //for(i=1;i<=n;i++)
        //if(articulation_vertex[i]==1)
            //out<<i<<"\n";
    fout<<cc<<'\n';
    for(int i=1; i<=cc; i++)
    {
        for(int j= 0; j<sol[i].size(); j++)
            fout<<sol[i][j]<<" ";
        fout<<'\n';
    }
    return 0;
}