Cod sursa(job #2681696)

Utilizator cyg_ieeuVasile Radu-Andrei cyg_ieeu Data 6 decembrie 2020 13:19:04
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
const int NMAX = 100000;
std::vector<int>g[NMAX + 3];
std::vector<int>discover,low,articulation,parent;
std::stack<std::pair<int,int>>st;
std::vector<int>sol[NMAX];
int time,root,children,sols;
void dfs(int u)
{
    int v;
    time++;
    discover[u] = low[u] = time;
    for(int i = 0;i < g[u].size();i++)
    {
        v = g[u][i];
        if(!discover[v])
        {
            st.push({u,v});
            parent[v] = u;
            if(u == root)
                children++;
            dfs(v);
            if(low[v] >= discover[u])
            {
                sols++;
                std::pair<int,int>aux = st.top();
                do
                {
                    sol[sols].push_back(st.top().second);
                    aux = st.top();
                    st.pop();
                }while(!(st.empty() || aux.first == u || aux.second == v));
                sol[sols].push_back(aux.first);
                articulation[u] = 1;
            }
            low[u] = std::min(low[u],low[v]);
        }
        else if(v != parent[u])
            low[u] = std::min(low[u],discover[v]);
    }
}
int main()
{
    int n,m,u,v;
    in>>n>>m;
    for(int i = 1;i <= m;i++)
    {
        in>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    discover.assign(n+1,0);
    low.assign(n+1,0);
    articulation.assign(n+1,0);
    parent.assign(n+1,0);
    for(int i = 1;i <= n;i++)
    {
        if(!discover[i])
        {
            sols = 0;
            root = i;
            children = 0;
            dfs(i);
            articulation[root] = (children>1);
        }
    }
    out<<sols<<'\n';
    for(int i = 1;i <= sols;i++)
    {
        for(int j = 0;j < sol[i].size();j++)
            out<<sol[i][j]<<' ';
        out<<'\n';
    }
    return 0;
}