Cod sursa(job #2794238)

Utilizator blxqnAlina Voiculescu blxqn Data 4 noiembrie 2021 15:33:00
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.7 kb
#include <bits/stdc++.h>
using namespace std;

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

class Graph
{
    int NumberOfNodes;
    int NumberOfEdges;
    bool Oriented;
    vector<vector<int>> AdjacencyList;

    public:
        Graph();
        Graph(int, int, bool);

        void Build();
        void BFS(int, int[]);
        void DFS(int, bool[]);
        int NumberOfConnectedComponents();
        void functionBCC(int, int, int[], int[], stack<int>&, bool[], vector<vector<int>>&);
        vector<vector<int>> BiconnectedComponents(int);
};


int main()
{
    int NumberOfNodes, NumberOfEdges;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 0);
    G.Build();

    vector<vector<int>> BCCs = G.BiconnectedComponents(0);
    fout << BCCs.size() << "\n";

    for (unsigned int i = 0; i < BCCs.size(); i++)
    {
        vector<int> BCC = BCCs[i];

        for (unsigned int j = 0; j < BCC.size(); j++)
        {
            int node = BCC[j] + 1;
            fout << node << " ";
        }
        fout << "\n";
    }

/*  ----------------------------DFS----------------------------
    int NumberOfNodes, NumberOfEdges;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(NumberOfNodes, NumberOfEdges, 0);
    G.Build();

    fout << G.NumberOfConnectedComponents();

    ----------------------------DFS----------------------------*/


/*  ----------------------------BFS----------------------------
    int NumberOfNodes, NumberOfEdges, StartNode;
    fin >> NumberOfNodes >> NumberOfEdges >> StartNode;

    Graph G(NumberOfNodes, NumberOfEdges, true);
    G.Build();

    int Distance[NumberOfNodes];
    StartNode--;
    G.BFS(StartNode, Distance);

    for (int i = 0; i < NumberOfNodes; i++)
        fout << Distance[i] << " ";

    ----------------------------BFS----------------------------*/

    fin.close();
    fout.close();

    return 0;
}




Graph::Graph() : NumberOfNodes(0), NumberOfEdges(0), Oriented(0) { }

Graph::Graph(int _NumberOfNodes, int _NumberOfEdges, bool _Oriented) : NumberOfNodes(_NumberOfNodes), NumberOfEdges(_NumberOfEdges), Oriented(_Oriented)
{
    NumberOfNodes = _NumberOfNodes;
    NumberOfEdges = _NumberOfEdges;
    Oriented = _Oriented;

    for (int i = 0; i < _NumberOfNodes; i++)
        AdjacencyList.push_back( {} );
        //AdjacencyList.push_back(vector<int>());
}

void Graph::Build()
{
    for (int i = 0; i < NumberOfEdges; i++)
    {
        int FirstNode, SecondNode;
        fin >> FirstNode >> SecondNode;
        FirstNode--;
        SecondNode--;

        AdjacencyList[FirstNode].push_back(SecondNode);
        if (!Oriented)
            AdjacencyList[SecondNode].push_back(FirstNode);
    }
}

void Graph::BFS(int StartNode, int Distance[])
{
    bool Visited[NumberOfNodes];
    queue<int> BFSQueue;

    for(int i = 0; i < NumberOfNodes; i++)
    {
        Visited[i] = 0;
        Distance[i] = -1;
    }

    Visited[StartNode] = 1;
    Distance[StartNode] = 0;
    BFSQueue.push(StartNode);

    while (!BFSQueue.empty())
    {
        int CurrentNode = BFSQueue.front();

        for (unsigned int i = 0; i < AdjacencyList[CurrentNode].size(); i++)
        {
            int AdjacentNode = AdjacencyList[CurrentNode][i];

            if (!Visited[AdjacentNode])
            {
                Visited[AdjacentNode] = 1;
                Distance[AdjacentNode] = Distance[CurrentNode] + 1;
                BFSQueue.push(AdjacentNode);
            }
        }
        BFSQueue.pop();
    }
}

void Graph::DFS(int StartNode, bool Visited[])
{
    Visited[StartNode] = 1;

    for (unsigned int i = 0; i < AdjacencyList[StartNode].size(); i++) //parcurg vecinii nodului
    {
        int NextNode = AdjacencyList[StartNode][i];
        if (!Visited[NextNode])
            DFS(NextNode, Visited);
    }
}

int Graph::NumberOfConnectedComponents()
{
    bool Visited[NumberOfNodes];
    int _NumberOfConnectedComponents = 0;

    for (int i = 0; i < NumberOfNodes; i++)
        Visited[i] = 0;

    for (int i = 0; i < NumberOfNodes; i++)
    {
        if (!Visited[i])
        {
            DFS(i, Visited);
            _NumberOfConnectedComponents++;
        }
    }

    return _NumberOfConnectedComponents;
}

vector<vector<int>> Graph::BiconnectedComponents(int Node)
{
    int id = 0, ids[NumberOfNodes], low[NumberOfNodes];
    bool onStack[NumberOfNodes];
    vector<vector<int>> BCCs;
    stack<int> Stack;

    for (int i = 0; i < NumberOfNodes; i++)
        onStack[i] = 0;

    functionBCC(Node, id, ids, low, Stack, onStack, BCCs);

    return BCCs;
}

void Graph::functionBCC(int Node, int id, int ids[], int low[], stack<int> &Stack, bool onStack[], vector<vector<int>> &BCCs)
{
    Stack.push(Node);
    onStack[Node] = 1;
    ids[Node] = low[Node] = id++;

    for (unsigned int i = 0; i < AdjacencyList[Node].size(); i++)
    {
        int AdjacentNode = AdjacencyList[Node][i];

        if (onStack[AdjacentNode])
            low[Node] = min(low[Node], ids[AdjacentNode]);
        else
        {
            functionBCC(AdjacentNode, id, ids, low, Stack, onStack, BCCs);

            low[Node] = min(low[Node], low[AdjacentNode]);

            if (low[AdjacentNode] >= ids[Node])
            {
                vector<int> BCC;
                int NodeBCC;

                BCC.push_back(Node);
                do {
                    NodeBCC = Stack.top();
                    BCC.push_back(NodeBCC);
                    Stack.pop();
                    } while (NodeBCC != AdjacentNode);

                BCCs.push_back(BCC);
            }
        }
    }
}