Cod sursa(job #2689820)

Utilizator dimi999Dimitriu Andrei dimi999 Data 22 decembrie 2020 12:54:02
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 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_biconex(int node)
{
    viz[node] = true;
    st.push(node);


    for(int i = 0; i < v[node].size(); i++)
        if(viz[v[node][i]] == false)
    {
        get_biconex(v[node][i]);

         if(dp[v[node][i]] == 0)
               {

                   vector <int> aux;

                   int x;

                    do
                     {
                         x = st.top();
                         st.pop();
                         aux.push_back(x);
                     }
                     while(x != v[node][i]);

                     //aux.push_back(node);

                    if(aux.size() >= 2)
                     elem.push_back(aux);

                     elem.push_back({node, 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);


    for(int i = 1; i <= N; i++)
        if(viz[i] == false)
        {
            get_biconex(i);

            vector <int> aux;

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

             if(aux.size() >= 2)
                    elem.push_back(aux);
        }

    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;
}