Cod sursa(job #2814028)

Utilizator atudoreimirunaAtudorei Miruna Gabriela atudoreimiruna Data 7 decembrie 2021 13:42:39
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define Max 100005

using namespace std;

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

int N, M;

int Stack[Max], top;
vector<int> biconnected_components[Max];
int number_of_biconnected_components;

class Graph{
private:
    int NumberOfNodes, NumberOfEdges;
    vector<int> adjacencyList[Max];
    
public:
    Graph(int N, int M); // constructor
    void Read_UndirectedGraph();
    void DFS_BiconnectedComponents(int, int, bool[], int[], int[]);
    void Write_BiconnectedComponents();
};

// constructor
Graph :: Graph(int N, int M)
{
    NumberOfNodes = N;
    NumberOfEdges = M;
}

void Graph :: Read_UndirectedGraph()
{
    for ( int i = 1; i <= NumberOfEdges; i++ )
    {
        int x, y;
        fin >> x >> y;
        adjacencyList[x].push_back(y);
        adjacencyList[y].push_back(x);
    }
}

void Graph :: DFS_BiconnectedComponents(int node, int parent, bool visited[], int up[], int levels[])
{
    visited[node] = 1;
    up[node] = levels[node];
    Stack[++top] = node; // adaugam nodul in stiva

    for ( auto i : adjacencyList[node] )
    {
        if ( i == parent ) continue;
        if ( visited[i] )
            up[node] = min(up[node], levels[i]);
        else
        {
            levels[i] = levels[node] + 1;
            DFS_BiconnectedComponents(i, node, visited, up, levels);
            if ( up[i] >= levels[node] )
            {
                number_of_biconnected_components++;
                while ( top && Stack[top] != i )
                    biconnected_components[number_of_biconnected_components].push_back(Stack[top--]);
                biconnected_components[number_of_biconnected_components].push_back(Stack[top--]);
                biconnected_components[number_of_biconnected_components].push_back(node);
            }
            up[node] = min(up[node], up[i]);
        }
    }
}

int main()
{
    fin >> N >> M;

    Graph G(N, M);
    G.Read_UndirectedGraph();

    G.DFS_BiconnectedComponents(1, 0, visited, up, levels);

    int j;
    fout << number_of_biconnected_components << "\n";
    for ( int i = 1; i <= number_of_biconnected_components; i++ )
    {
        for ( auto j : biconnected_components[i] )
            fout << j << " ";
        fout << "\n";
    }
    return 0;
}