Cod sursa(job #2672042)

Utilizator killerdonuttudor nicolae killerdonut Data 12 noiembrie 2020 23:07:02
Problema Componente biconexe Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

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

//const int N_MAX = 1e5 + 1;
const int N_MAX = 9;

struct ReindexedVertex{
    int index, indexProcessed = -1, lowlink;
    bool onStack = false;
};

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

stack <pair <int, int>> stk;

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

void GenerateBiconexComponent(int parentIndex)
{
    unordered_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;
    node.onStack = true;

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

            if(neighbor.lowlink >= node.indexProcessed)
            {
                GenerateBiconexComponent(node.index);
            }
        }
        else if(neighbor.indexProcessed != -1)
        {
            node.lowlink = min(neighbor.indexProcessed, node.lowlink);
        }        
    }
}

int main()
{
    int n, m;

    fin >> n >> m;

    graphVertexes.resize(n + 1);
    for(int i = 1; i <= n; i++)
    {
        graphVertexes[i].index = i;
    }

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

    for(int i = 1; i <= n; i++)
    {
        if(graphVertexes[i].indexProcessed != -1)
            continue;

        FindArticulationPoints(i, 1);
    }


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

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

        fout << '\n';
    }

    return 0;
}