Cod sursa(job #2802641)

Utilizator blxqnAlina Voiculescu blxqn Data 18 noiembrie 2021 16:18:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 20.07 kb
#include <bits/stdc++.h>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const int MAX = 100000;

class Graph
{
    int numberOfNodes;
    int numberOfEdges;
    bool oriented;
    vector<vector<int>> adjacencyList;
    vector<pair<int, int>> adjacencyListWeightedGraph[MAX];

    void DFS(int, bool[]);

    void _BiconnectedComponents(int, int, int[], int[], stack<int>&, bool[], vector<vector<int>>&);

    void _StronglyConnectedComponents(int, int&, int[], int[], stack<int>&, bool[], bool[], vector<vector<int>>&);

    void _TopologicalSort(int, bool[], vector<int>&);

    void _CriticalConnections(int, bool[], int[], int[], int[], vector<vector<int>>&);


    public:
        Graph();
        Graph(int, int, bool);
        void Build();
        void BuildFromVector(vector<vector<int>>);
        void BuildWeightedGraph();
        int GetNumberOfNodes();
        int GetNumberOfEdges();

        void BFS(int, int[]);

        int NumberOfConnectedComponents();

        vector<vector<int>> BiconnectedComponents(int);

        vector<vector<int>> StronglyConnectedComponents();

        vector<int> TopologicalSort();

        //Checks if a graph exists
        bool HavelHakimi(vector<int>&);

        vector<vector<int>> CriticalConnections();

        //Prim's Minimum Spanning Tree
        void MinimumSpanningTree(int);

        void Dijkstra(int);

        void BellmanFord(int);
};

//LeetCode Critical Connections Problem
class Solution {
public:
    vector<vector<int>> CriticalConnections(int n, vector<vector<int>>& connections)
    {
        Graph G(n, connections.size(), 0);
        G.BuildFromVector(connections);

        return G.CriticalConnections();
    }
};

int main()
{
/*  ----------------------------BellmanFord----------------------------
    int numberOfNodes, numberOfEdges, startNode;
    fin >> NumberOfNodes >> NumberOfEdges;

    Graph G(numberOfNodes, numberOfEdges, 1);
    G.BuildWeightedGraph();

    startNode = 0;
    G.BellmanFord(startNode);
    ----------------------------BellmanFord----------------------------*/



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

    Graph G(NumberOfNodes, NumberOfEdges, 1);
    G.BuildWeightedGraph();

    StartNode = 0;
    G.Dijkstra(StartNode);
    ----------------------------Dijkstra----------------------------*/



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

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

    StartNode = 0;
    G.MinimumSpanningTree(StartNode);
    ----------------------------APM----------------------------*/



/*  ----------------------------CCs----------------------------

    Solution S;
    int n = 4;
    vector<vector<int>> connections = {{0,1},{1,2},{2,0},{1,3}}, CCs;

    CCs = S.criticalConnections(n, connections);

    for (unsigned int i = 0; i < CCs.size(); i++)
        cout << "Critical connection " << i + 1 << ": " << CCs[i][0] << " - " << CCs[i][1] << "\n";

    ----------------------------CCs----------------------------*/



/*  ----------------------------HH----------------------------

    Graph G;
    vector<int> Degrees = {5,5,5,3,2,2,2};

    if (G.functionHavelHakimi(Degrees))
        cout << "Yes";
    else
       cout << "No";

    ----------------------------HH----------------------------*/



/*  ----------------------------TS----------------------------

    int NumberOfNodes, NumberOfEdges;
    fin >> NumberOfNodes >> NumberOfEdges;

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

    vector<int> TopologicalSort = G.TopologicalSort();

    reverse(TopologicalSort.begin(), TopologicalSort.end());

    for (auto Node : TopologicalSort)
        fout << Node + 1 << " ";

    ----------------------------TS----------------------------*/


/*  ----------------------------SCCs----------------------------

    int NumberOfNodes, NumberOfEdges;
    fin >> NumberOfNodes >> NumberOfEdges;

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

    vector<vector<int>> SCCs = G.StronglyConnectedComponents();
    fout << SCCs.size() << "\n";

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

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

    ----------------------------SCCs----------------------------*/


/*  ----------------------------BCCs----------------------------

    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";
    }

    ----------------------------BCCs----------------------------*/


///*  ----------------------------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, 1);
    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::BuildFromVector(vector<vector<int>> edges)
{
    for(unsigned int i = 0; i < edges.size(); i++)
    {
        int firstNode, secondNode;
        firstNode = edges[i][0];
        secondNode = edges[i][1];

        adjacencyList[firstNode].push_back(secondNode);
        if (!oriented)
            adjacencyList[secondNode].push_back(firstNode);

    }
}

void Graph::BuildWeightedGraph()
{
    for (int i = 0; i < numberOfEdges; i++)
    {
        int firstNode, secondNode, weight;
        fin >> firstNode >> secondNode >> weight;
        firstNode--;
        secondNode--;

        adjacencyListWeightedGraph[firstNode].push_back(make_pair(secondNode, weight));

        if (!oriented)
            adjacencyListWeightedGraph[secondNode].push_back(make_pair(firstNode, weight));
    }
}

int Graph::GetNumberOfNodes()
{
    return numberOfNodes;
}

int Graph::GetNumberOfEdges()
{
    return numberOfEdges;
}

void Graph::BFS(int startNode, int distance[])
{
    bool visited[numberOfNodes];
    queue<int> queueBFS;

    for(int i = 0; i < numberOfNodes; i++)
    {
        visited[i] = 0;
        distance[i] = -1;
    }

    visited[startNode] = 1;
    distance[startNode] = 0;
    queueBFS.push(startNode);

    while (!queueBFS.empty())
    {
        int currentNode = queueBFS.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;
                queueBFS.push(adjacentNode);
            }
        }
        queueBFS.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;
}

void Graph::_BiconnectedComponents(int node, int id, int ids[], int low[], stack<int> &stackBiconnectedComponents, bool visited[], vector<vector<int>> &biconnectedComponents)
{
    stackBiconnectedComponents.push(node);
    visited[node] = 1;
    ids[node] = low[node] = id++;

    for (unsigned int i = 0; i < adjacencyList[node].size(); i++)
    {
        int adjacentNode = adjacencyList[node][i];

        if (visited[adjacentNode])
            low[node] = min(low[node], ids[adjacentNode]);
        else
        {
            _BiconnectedComponents(adjacentNode, id, ids, low, stackBiconnectedComponents, visited, biconnectedComponents);

            low[node] = min(low[node], low[adjacentNode]);

            if (low[adjacentNode] >= ids[node])
            {
                vector<int> biconnectedComponent;
                int nodeBiconnectedComponent;

                do {
                    nodeBiconnectedComponent = stackBiconnectedComponents.top();
                    biconnectedComponent.push_back(ids[nodeBiconnectedComponent]);
                    stackBiconnectedComponents.pop();
                    } while (nodeBiconnectedComponent != adjacentNode);
                biconnectedComponent.push_back(node);

                biconnectedComponents.push_back(biconnectedComponent);
            }
        }
    }
}

void Graph::_StronglyConnectedComponents(int node, int &id, int ids[], int low[], stack<int> &stackStronglyConnectedComponents, bool onStack[], bool visited[], vector<vector<int>> &stronglyConnectedComponents)
{
    stackStronglyConnectedComponents.push(node);
    onStack[node] = 1;
    visited[node] = 1;
    ids[node] = low[node] = id++;

    for (unsigned int i = 0; i < adjacencyList[node].size(); i++)
    {
        int adjacentNode = adjacencyList[node][i];

        if (!visited[adjacentNode])
        {
            _StronglyConnectedComponents(adjacentNode, id, ids, low, stackStronglyConnectedComponents, onStack, visited, stronglyConnectedComponents);

            low[node] = min(low[node], low[adjacentNode]);
        }
        else if (onStack[adjacentNode])
            low[node] = min(low[node], low[adjacentNode]);
    }

    if (ids[node] == low[node])
    {
        vector<int> stronglyConnectedComponent;
        int nodeStronglyConnectedComponent;

        do {
            nodeStronglyConnectedComponent = stackStronglyConnectedComponents.top();
            stronglyConnectedComponent.push_back(nodeStronglyConnectedComponent);
            stackStronglyConnectedComponents.pop();
            onStack[nodeStronglyConnectedComponent] = 0;
            } while (nodeStronglyConnectedComponent != node);

        stronglyConnectedComponents.push_back(stronglyConnectedComponent);
    }
}

vector<vector<int>> Graph::BiconnectedComponents(int node)
{
    int id = 0, ids[numberOfNodes], low[numberOfNodes];
    bool visited[numberOfNodes];
    vector<vector<int>> biconnectedComponents;
    stack<int> stackBiconnectedComponents;

    for (int i = 0; i < numberOfNodes; i++)
        visited[i] = 0;

    _BiconnectedComponents(node, id, ids, low, stackBiconnectedComponents, visited, biconnectedComponents);

    return biconnectedComponents;
}

vector<vector<int>> Graph::StronglyConnectedComponents()
{
    int id = 0, ids[numberOfNodes], low[numberOfNodes];
    bool onStack[numberOfNodes], visited[numberOfNodes];
    vector<vector<int>> stronglyConnectedComponents;
    stack<int> stackStronglyConnectedComponents;

    for (int i = 0; i < numberOfNodes; i++)
    {
        onStack[i] = 0;
        visited[i] = 0;
    }

    for (int i = 0; i < numberOfNodes; i++)
        if (!visited[i])
            _StronglyConnectedComponents(i, id, ids, low, stackStronglyConnectedComponents, onStack, visited, stronglyConnectedComponents);

    return stronglyConnectedComponents;
}

void Graph::_TopologicalSort(int startNode, bool visited[], vector<int> &topologicalSort)
{
    visited[startNode] = 1;

    for (unsigned int i = 0; i < adjacencyList[startNode].size(); i++) //parcurg vecinii nodului
    {
        int nextNode = adjacencyList[startNode][i];
        if (!visited[nextNode])
            _TopologicalSort(nextNode, visited, topologicalSort);
    }
    topologicalSort.push_back(startNode);
}


vector<int> Graph::TopologicalSort()
{
    vector<int> topologicalSort;
    bool visited[numberOfNodes];

    for(int i = 0; i < numberOfNodes; i++)
        visited[i] = 0;

    for(int i = 0; i < numberOfNodes; i++)
        if(!visited[i])
            _TopologicalSort(i, visited, topologicalSort);

    return topologicalSort;
}

bool Graph::HavelHakimi(vector<int> &degrees)
{
    numberOfNodes = degrees.size();
    sort(degrees.begin(), degrees.end(), greater<>());

    if (numberOfNodes < 1 || degrees[0] == 0)
        return 1;

    if (accumulate(degrees.begin(), degrees.end(), 0) % 2)
        return 0;

    if (degrees[0] > numberOfNodes - 1)
        return 0;

    int element = degrees[0];
    degrees.erase(degrees.begin() + 0);

    for (int i = 0; i < element; i++)
    {
        if(degrees[i] > 0)
            degrees[i]--;
        else
            return 0;
    }

    return HavelHakimi(degrees);
}

void Graph::_CriticalConnections(int node, bool visited[], int disc[], int low[], int parent[], vector<vector<int>> &criticalConnections)
{
    static int time = 0;

    visited[node] = 1;
    disc[node] = low[node] = ++time;

    for (unsigned int i = 0; i < adjacencyList[node].size(); i++)
    {
        int adjacentNode = adjacencyList[node][i];

        if (!visited[adjacentNode])
        {
            parent[adjacentNode] = node;
            _CriticalConnections(adjacentNode, visited, disc, low, parent, criticalConnections);

            low[node] = min(low[node], low[adjacentNode]);

            if(low[adjacentNode] > disc[node])
            {
                vector<int> criticalConnection;

                criticalConnection.push_back(node);
                criticalConnection.push_back(adjacentNode);

                criticalConnections.push_back(criticalConnection);
            }
        }
        else if (adjacentNode != parent[node])
            low[node] = min (low[node], disc[adjacentNode]);
    }
}

vector<vector<int>> Graph::CriticalConnections()
{
    vector<vector<int>> criticalConnections;
    bool visited[numberOfNodes];
    int disc[numberOfNodes], low[numberOfNodes], parent[numberOfNodes];

    for (int i = 0; i < numberOfNodes; i++)
    {
        parent[i] = -1;
        visited[i] = 0;
    }

    for (int i = 0; i < numberOfNodes; i++)
        if (!visited[i])
            _CriticalConnections(i, visited, disc, low, parent, criticalConnections);

    return criticalConnections;
}

void Graph::MinimumSpanningTree(int startNode)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    int totalCost = 0, minimumSpanningTreeEdges = 0;
    vector<int> key(numberOfNodes, INF);
    vector<int> parent(numberOfNodes, -1);
    vector<bool> inMST(numberOfNodes, 0);

    minHeap.push(make_pair(0, startNode));
    key[startNode] = 0;

    while(!minHeap.empty())
    {
        int node = minHeap.top().second;
        minHeap.pop();

        if(!inMST[node])
        {
            inMST[node] = 1;

            for (auto i : adjacencyListWeightedGraph[node])
            {
                int adjacentNode = i.first;
                int weight = i.second;

                if (!inMST[adjacentNode] && weight < key[adjacentNode])
                {
                    if (key[adjacentNode] != INF)
                        totalCost -= key[adjacentNode];
                    else
                        minimumSpanningTreeEdges++;

                    key[adjacentNode] = weight;
                    parent[adjacentNode] = node;
                    minHeap.push(make_pair(key[adjacentNode], adjacentNode));

                    totalCost += key[adjacentNode];
                }
            }
        }
    }

    fout << totalCost << "\n" << minimumSpanningTreeEdges << "\n";

    for (int i = 1; i < numberOfNodes; i++)
        fout << parent[i] + 1 << " " << i + 1 << "\n";
}

void Graph::Dijkstra(int startNode)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    vector<int> key(numberOfNodes, INF);
    vector<bool> inDijkstra(numberOfNodes, 0);

    minHeap.push(make_pair(0, startNode));
    key[startNode] = 0;

    while(!minHeap.empty())
    {
        int node = minHeap.top().second;
        minHeap.pop();

        if(!inDijkstra[node])
        {
            inDijkstra[node] = 1;

            for (auto i : adjacencyListWeightedGraph[node])
            {
                int adjacentNode = i.first;
                int adjacentNodeWeight = i.second;

                if (key[node] + adjacentNodeWeight < key[adjacentNode])
                {
                    key[adjacentNode] = key[node] + adjacentNodeWeight;
                    minHeap.push(make_pair(key[adjacentNode], adjacentNode));
                }
            }
        }
    }

    for (int i = 0; i < numberOfNodes; i++)
    {
        if (i != startNode)
        {
            if (key[i] == INF)
            {
                key[i] = 0;
            }
            fout << key[i] << " ";
        }
    }
}

void Graph::BellmanFord(int startNode)
{
    vector<int> key(numberOfNodes, INF);
    queue<int> queueBF;
    long long int iterations = 0;
    bool negativeCycle = 0;

    key[startNode] = 0;
    queueBF.push(startNode);

    while (!queueBF.empty())
    {
        if (iterations > (long long int)(numberOfNodes - 1) * numberOfEdges)
        {
            negativeCycle = 1;
            break;
        }

        int node = queueBF.front();
        queueBF.pop();

        for (auto i : adjacencyListWeightedGraph[node])
        {
            int adjacentNode = i.first;
            int adjacentNodeWeight = i.second;

            if (key[node] + adjacentNodeWeight < key[adjacentNode])
            {

                key[adjacentNode] = key[node] + adjacentNodeWeight;
                queueBF.push(adjacentNode);
            }
        }
        iterations++;
    }

    if (negativeCycle)
        fout << "Ciclu negativ!";
    else
        for (int i = 0; i < numberOfNodes; i++)
            if (i != startNode)
            {
                if (key[i] == INF)
                    key[i] = 0;
                fout << key[i] << " ";
            }
}