Cod sursa(job #2689831)

Utilizator dimi999Dimitriu Andrei dimi999 Data 22 decembrie 2020 13:25:39
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
using namespace std;

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

vector <int> v[100005];

int lvl[100005], dp[100005];

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

   // if(node == 19636)
       // return;

    int sz = v[node].size();

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

bool viz[100005];

stack <int> st;

vector < vector <int> > elem;

vector <int> aux;

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

    //if(node == 19636)
        //return;


    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)
               {

                   aux.clear();

                   int x;

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

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


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

            aux.clear();

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