Cod sursa(job #2564590)

Utilizator ArkinyStoica Alex Arkiny Data 1 martie 2020 23:57:18
Problema Componente biconexe Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb

#include<fstream>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

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

vector<vector<int> > components;

vector<int> G[100010];

int M[100010][2];
int viz[100010];

int nr = 0;

vector<int> stack;


void tarjan(int x, int f)
{
    ++nr;
    viz[x] = 1;

    M[x][0] = M[x][1] = nr;

    stack.push_back(x);

    for (auto& neighbor : G[x])
    {
        if (!viz[neighbor])
        {
            tarjan(neighbor, x);

            M[x][1] = min(M[x][1], M[neighbor][1]);


            if (M[x][0] <= M[neighbor][1])
            {
                vector<int> comp;
                while (stack.back() != neighbor)
                {
                    comp.push_back(stack.back());
                    stack.pop_back();
                }

                comp.push_back(neighbor);

                comp.push_back(x);

                comp.pop_back();

                components.push_back(comp);
            }
        }
        else if (neighbor != f)
        {
            M[x][1] = min(M[x][1], M[neighbor][1]);
        }
    }


}

int main()
{
    int N, M;

    in >> N >> M;

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

        in >> x >> y;

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

    tarjan(1, 0);


    out << components.size() << "\n";

    for (auto& comp : components)
    {
        for (auto& node : comp)
        {
            out << node << " ";
        }

        out << "\n";
    }


    return 0;
}