Cod sursa(job #2672076)

Utilizator killerdonuttudor nicolae killerdonut Data 12 noiembrie 2020 23:58:08
Problema Componente biconexe Scor 52
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define node graphVertexes[nodeIndex]
#define neighbor graphVertexes[neighborIndex]
#define nextAvailableIndex availableIndex + 1

const int N_MAX = 1e5 + 1;

struct ReindexedVertex{
    int indexProcessed = -1, lowlink;
};

vector <int> graph[N_MAX];
vector <ReindexedVertex> graphVertexes;
vector <set <int>> solutions;

stack <pair <int, int>> stk;

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

void GenerateBiconexComponent(int parentIndex)
{
    set<int> sol;
    int st, dr;
 
    while(st != parentIndex)
    {
        st = stk.top().first;
        dr = stk.top().second;
        stk.pop();
        sol.insert(st);
        sol.insert(dr);
    }

    solutions.push_back(sol);
}

void FindArticulationPoints(int nodeIndex, int availableIndex)
{
    node.indexProcessed = availableIndex;
    node.lowlink = availableIndex;

    for(auto neighborIndex: graph[nodeIndex])
    {
        if(neighbor.indexProcessed == -1)
        {
            stk.push(make_pair(nodeIndex, neighborIndex));
            FindArticulationPoints(neighborIndex, nextAvailableIndex);
            node.lowlink = min(neighbor.lowlink, node.lowlink);

            if(neighbor.lowlink >= node.indexProcessed)
            {
                GenerateBiconexComponent(nodeIndex);
            }
        }
        else
        {
            node.lowlink = min(neighbor.indexProcessed, node.lowlink);
        }        
    }
}

int main()
{
    int n, m;

    fin >> n >> m;

    graphVertexes.resize(n + 1);

    for(int i = 0, st, dr; i < m; i++)
    {
        fin >> st >> dr;
        graph[st].push_back(dr);
        graph[dr].push_back(st);
    }


    FindArticulationPoints(1, 1);

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

    for(auto sol: solutions)
    {
        for(auto val: sol)
        {
            fout << val << ' ';
        }

        fout << '\n';
    }

    return 0;
}