Cod sursa(job #2394075)

Utilizator btudorBazac Tudor btudor Data 1 aprilie 2019 12:01:58
Problema Componente biconexe Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

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

vector <int> g[100001];
vector <int> dfs_discover,dfs_low,articulation_vertex,dfs_parent;
stack < pair<int,int> > st;
vector <int> graf[100001];

int tim,dfsroot,rootchildren,n,numar=1;

void golire(int u,int v)
{
    int i=0,j=0;
    graf[numar].push_back(st.top().second);
    do
    {
        i=st.top().first;
        j=st.top().second;
        graf[numar].push_back(i);
        st.pop();
    }while(i!=u && j!=v);
    numar++;
}

void articulationpoint(int u)
{
    int v,j;
    tim++;
    dfs_discover[u]=tim;
    dfs_low[u]=tim;
    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;
                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,j;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>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;
        }
    numar--;
    out<<numar<<"\n";
    for(i=1;i<=numar;i++)
    {
        for(j=0;j<graf[i].size();j++)
            out<<graf[i][j]<<" ";
        out<<"\n";
    }
    return 0;
}