Cod sursa(job #2689808)

Utilizator dimi999Dimitriu Andrei dimi999 Data 22 decembrie 2020 12:25:01
Problema Componente biconexe Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <bits/stdc++.h>
using namespace std;

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

vector <int> v[100005];

bool is_articulation[100005];

int lvl[100005], dp[100005];

void get_articulation(int node, int dad, int nivel)
{
    lvl[node] = nivel;

    for(int i = 0; i < v[node].size(); i++)
        if(v[node][i] != dad && lvl[v[node][i]] == 0)
    {
        get_articulation(v[node][i], node, nivel + 1);
        dp[node] += dp[v[node][i]];
    }
    else
        if(v[node][i] != dad && lvl[v[node][i]] > nivel)
            dp[node] ++;
    else
        if(v[node][i] != dad)
            dp[node]--;

    //if(dp[node] == 0)
        //is_articulation[dad] = true;
}

bool viz[100005];

stack <int> st;

vector < vector <int> > elem;

void get_stack()
{
    if(st.size() >= 2)
    {
        vector <int> aux;

        while(!st.empty())
        {
            aux.push_back(st.top());
            st.pop();
        }

        elem.push_back(aux);
    }
}

void get_biconex(int node)
{
    viz[node] = true;
    st.push(node);


    for(int i = 0; i < v[node].size(); i++)
        if(viz[v[node][i]] == false)
    {
        if(dp[v[node][i]] == 0)
            {
                elem.push_back({node, v[node][i]});

                get_stack();
            }
        get_biconex(v[node][i]);
    }
}

int main()
{
    int N, M;

    fin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y;

        fin >> x >> y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    get_articulation(1, 0, 1);

    get_biconex(1);

    get_stack();

    fout << elem.size() << '\n';

    for(int i = 0; i < elem.size(); i++)
    {
        for(int j = 0; j < elem[i].size(); j++)
            fout << elem[i][j] << " ";
        fout << '\n';
    }
    return 0;
}