Cod sursa(job #2797599)

Utilizator faalaviaFlavia Podariu faalavia Data 10 noiembrie 2021 11:34:23
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 10.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <sys/resource.h>
using namespace std;
 
class Graph {
    int nrNodes; //number of nodes
    vector<vector< pair<int, double>> > edges; // list of connections between nodes
public:
    Graph(int _nrNodes);
    int getNrNodes() const;
    void setEdge(int node, int neighbour, double cost);
    vector<pair<int, double>>getNeighbours(int node);
    int nrConnectedComponents();
    void printEdges();
    vector<int> minDistanceBFS(int start);
    ~Graph();
private:
    void DFS(int node, vector<int>& visited);
 
};
 
//---------------------------------------------
 
Graph::Graph(int _nrNodes)
{
    this -> nrNodes = _nrNodes;
    this -> edges.resize(this -> nrNodes + 1, vector<pair<int, double>>());
    /*
     * Nodes start at 1, but index starts at 0
     */
}
 
int Graph::getNrNodes() const
{
    return this -> nrNodes;
}
 
int Graph::nrConnectedComponents()
{
    int ans = 0;
    vector<int>visited(this -> nrNodes+1, 0);
    for(int i = 1 ; i <= this -> nrNodes; ++i)
        if(visited[i] == 0)
        {
            DFS(i, visited);
            ++ans;
        }
    return ans;
}
 
 
void Graph::DFS(int start, vector<int>& visited)
{
    visited[start] = 1;
    for(int i = 0; i < edges[start].size(); ++i)
    {
        int neighbour = edges[start][i].first; // get neighbour without cost
        if(visited[neighbour] == 0)
        {
            visited[neighbour] = 1;
            DFS(neighbour, visited);
        }
    }
}
 
Graph::~Graph()
{
    this -> nrNodes = 0;
    for(int i = 1; i <= edges.size(); ++i)
        this -> edges[i].clear();
}
 
void Graph::printEdges()
{
  for(int i = 1; i < edges.size(); i++)
  {
      cout << i<< ": ";
      for(auto it: edges[i])
          cout << it.first<< " ";
      cout << "\n";
  }
}
 
void Graph::setEdge(int node, int neighbour, double cost)
{
   this ->edges[node].push_back({neighbour, cost});
}
 
vector<int> Graph::minDistanceBFS(int start)
{
    vector<int>distances(this->nrNodes + 1, -1);
    distances[start] = 0;
 
    queue<int>toBeVisited;
    toBeVisited.push(start);
 
    while(!toBeVisited.empty())
    {
        int x = toBeVisited.front();
        toBeVisited.pop();
 
        for(auto it: this->edges[x])
            if(distances[it.first] == -1)
            {
                distances[it.first] = distances[x] + 1;
                toBeVisited.push(it.first);
            }
 
 
    }     //while loop ended
 
    return distances;
}
 
vector<pair<int, double>> Graph::getNeighbours(int node)
{
    return this -> edges[node];
}
 
//-------------------------------------------------------------------
 
class DirectedGraph: public Graph {
    void TarjanDFS(int start, int& counterID,
                          stack<int>&nodeStack, vector<bool>&onStack,
                          vector<vector<int>>&scc,
                          vector<int>&nodeID, vector<int>&lowestLink);
    void TopologicalDFS(int node, stack<int>&sorted,
                        vector<bool>&visited);
public:
    DirectedGraph(int _nrNodes);
    void addEdge(int node, int neighbour, double cost);
    vector<vector<int>> getStronglyConnected();
    stack<int> TopologicalSorting();
   ~DirectedGraph();
};
//----------------------------------------------------------------------
 
 
DirectedGraph::DirectedGraph(int _nrNodes): Graph(_nrNodes) {}
 
void DirectedGraph::addEdge(int node, int neighbour, double cost)
{
    this -> setEdge(node, neighbour, cost);
}
 
vector<vector<int>> DirectedGraph::getStronglyConnected()
{ // initializing everything we need for the Tarjan algorithm
    vector<vector<int>> scc;
    stack<int> nodeStack;
    vector<bool> onStack(this -> getNrNodes()+1, false);
    vector<int> lowestLink(this -> getNrNodes()+1, -1);
    vector<int> nodeID(this -> getNrNodes()+1, -1);
    int counterID = 0;
    for(int node = 1; node <= this -> getNrNodes(); ++node)
        if(nodeID[node] == -1)
            TarjanDFS(node, counterID, nodeStack,
                      onStack, scc, nodeID, lowestLink);
    /*
     * scc = strongly connected component
     * TarjanDFS() modifies vector<vector<int>> scc
     * so vector<vector<int>> scc will contain all the needed components
     */
 
    return scc;
}
 
void DirectedGraph::TarjanDFS(int node, int& counterID,
                              stack<int>&nodeStack,
                              vector<bool>& onStack,
                              vector<vector<int>>&scc,
                              vector<int> &nodeID,
                              vector<int>&lowestLink)
{
    vector<int> component;
    nodeID[node] = counterID;
    lowestLink[node] = counterID++;
    nodeStack.push(node);
    onStack[node] = true;
 
    for(auto it: this->getNeighbours(node))
    {
        int neighbour = it.first; // node -> first; cost -> second
        if(nodeID[neighbour] == -1)         // if neighbour not visited
            TarjanDFS(neighbour, counterID, nodeStack,
                      onStack, scc, nodeID,
                      lowestLink);
        if(onStack[neighbour])          //if neighbour is on stack
            lowestLink[node] = min(lowestLink[node], lowestLink[neighbour]);
    }
 
    if(lowestLink[node] == nodeID[node])  // if this is true then node is the beginning of a scc
    {
        while(!nodeStack.empty())
        {
            int nodeToPop = nodeStack.top();
            component.push_back(nodeToPop);
            onStack[nodeToPop] = false;
            nodeStack.pop();
            if(nodeToPop == node)
                break;
        }
 
        scc.push_back(component);
        component.clear();
    }
}
 
 
DirectedGraph::~DirectedGraph() {}
 
stack<int> DirectedGraph::TopologicalSorting()
{
    stack<int> sorted;
    vector<bool> visited(this->getNrNodes() + 1, false);
    for(int node = 1; node < visited.size(); ++node)
        if(!visited[node])
            TopologicalDFS(node, sorted, visited);
    /*
     * -> TopologicalDFS() modifies the sorted vector
     * -> the sorted nodes are the nodes' times in descending order
     */
    return sorted;
}
 
void DirectedGraph::TopologicalDFS(int node, stack<int>&sorted,
                                   vector<bool>&visited)
{
   visited[node] = true;
   for(auto it: this->getNeighbours(node))
   {
       int neighbour = it.first;
       if (!visited[neighbour])
           TopologicalDFS(neighbour, sorted, visited);
 
   }
   sorted.push(node);
}
//---------------------------------------------------------------------------------
 
class UndirectedGraph: public Graph{
private:
    void BiconnectedDFS(int node, int counterID,
                        vector<int>&lowestLink, vector<int>&nodeID,
                        stack<int>&nodeStack,vector<vector<int>>&bcc,
                        int father);
    void addBiconnected(stack<int>&nodeStack, vector<vector<int>>&bcc,
                               int node, int neighbour);
public:
    UndirectedGraph(int _nrNodes);
    void addEdge(int node, int neighbour, double cost);
    ~UndirectedGraph();
    vector<vector<int>>biconnectedComponents();
};
 
UndirectedGraph::UndirectedGraph(int _nrNodes): Graph(_nrNodes){}
 
void UndirectedGraph::addEdge(int node, int neighbour, double cost)
{
    this -> setEdge(node, neighbour, cost);
    this -> setEdge(neighbour, node, cost);
}
 
UndirectedGraph::~UndirectedGraph() {}
 
vector<vector<int>> UndirectedGraph::biconnectedComponents()
{
    vector<vector<int>>bcc;
    stack<int> nodeStack;
    vector<bool> onStack(this -> getNrNodes()+1, false);
    vector<int> lowestLink(this -> getNrNodes()+1, -1);
    vector<int> nodeID(this -> getNrNodes()+1, -1);
    int counterID = 0;
    for(int node = 1; node <= this -> getNrNodes(); ++node)
        if(nodeID[node] == -1)
        {
            nodeStack.push(node);
            BiconnectedDFS(node, counterID,
                           lowestLink, nodeID,
                           nodeStack, bcc, -1);
        }
    return bcc;
}
 
void UndirectedGraph::BiconnectedDFS(int node, int counterID,
                                     vector<int> &lowestLink,
                                     vector<int> &nodeID,
                                     stack<int> &nodeStack,
                                     vector<vector<int>> &bcc,
                                     int father)
{
    nodeID[node] = counterID;
    lowestLink[node] = counterID++;
    nodeStack.push(node);
    for (auto it: this->getNeighbours(node))
    {
        int neighbour = it.first;
        if (nodeID[neighbour] == -1 && neighbour != father)
        {
 
            BiconnectedDFS(neighbour, counterID,
                           lowestLink, nodeID,
                           nodeStack, bcc, node);
            lowestLink[node] = min(lowestLink[node], lowestLink[neighbour]);
 
            if (lowestLink[neighbour] >= nodeID[node]) //node is an articulation point
              addBiconnected(nodeStack, bcc, node, neighbour);
        }
        else if (neighbour != father)
            lowestLink[node] = min(lowestLink[node], nodeID[neighbour]);
 
 
    }
}
 
void UndirectedGraph::addBiconnected(stack<int> &nodeStack, vector<vector<int>>&bcc,
                                            int node, int neighbour)
{
    /*
     * we stop popping at neighbour because between
     * neighbour and node (child and parent) there
     * might be other children of parent.
     * we then add neighbour and node to component
     * leaving node on stack as it might be part of
     * other components
     */
    vector<int>component;
    while (nodeStack.top() != neighbour)
    {
        component.push_back(nodeStack.top());
        nodeStack.pop();
    }
    nodeStack.pop();
    component.push_back(neighbour);
    component.push_back(node);
    bcc.push_back(component);
    component.clear();
}
//--------------------------------------------------------------------------------
int main()
{   

    const rlim_t new_stacksize = 20000000;
    struct rlimit limit;

    getrlimit(RLIMIT_STACK, &limit);

    limit.rlim_cur = new_stacksize;
    setrlimit(RLIMIT_STACK, &limit);

    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n, m, x, y,s;
    fin >> n >> m;
    UndirectedGraph *ug = new UndirectedGraph(n);
    for(int i = 1; i <= m; i++)
    {
     fin >> x >> y;
        ug -> addEdge(x, y, 0);
    }
 
   vector<vector<int>> bcc = ug -> biconnectedComponents();
   fout << bcc.size()<< "\n";
   for(auto it : bcc)
   {
       for(auto itt: it)
           fout << itt << " ";
       fout << "\n";
   }
 
    return 0;
 
}