Cod sursa(job #2927635)

Utilizator asparagusNadu Toma asparagus Data 20 octombrie 2022 22:41:11
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <iostream>
#include <bits/stdc++.h>

using namespace std;


void firstDFS(int node, vector<int> *adjacencyList, bool *isVisited, stack<int> *stack) {
    isVisited[node] = true;

    for (auto adjacentNode : adjacencyList[node])
        if (not isVisited[node])
            firstDFS(adjacentNode, adjacencyList, isVisited, stack);

    stack->push(node);
}


void secondDFS(int node, vector<int> *adjacencyList, bool *isVisited, string *toBeWritten) {
    isVisited[node] = true;

    for (auto adjacentNode : adjacencyList[node])
        if (not isVisited[node])
            secondDFS(adjacentNode, adjacencyList, isVisited, toBeWritten);

    *toBeWritten = *toBeWritten + " " + to_string(node);
}


void writeSCCs(int numberOfNodes, vector<int> *adjacencyList) {
    bool isVisited[numberOfNodes];
    for (int node=0; node<numberOfNodes; node++)
        isVisited[node] = false;

    stack<int> topologicalOrderingOfSCCs;

    // first DFS, used to find the topological ordering of the underlying graph's SCCs
    for (int node=0; node<numberOfNodes; node++)
        if (not isVisited[node])
            firstDFS(node, adjacencyList, isVisited, &topologicalOrderingOfSCCs);

    // marking all nodes as not visited, in preparation for the second DFS
    for (int node=0; node<numberOfNodes; node++)
        isVisited[node] = false;

    vector<int> transposedAdjacencyList[numberOfNodes];     // needed to store the adjacency list of the transposed graph

    // storing the adjacency list of the transposed graph
    for (int node=0; node<numberOfNodes; node++)
        for (auto adjacentNode : adjacencyList[node])
            transposedAdjacencyList[adjacentNode].push_back(node);

    string toBeWritten;
    int numberOfSCCs = 0;

    // second DFS, used to find SCCs (in reverse-topological order of the transposed graph's SCCs)
    while (not topologicalOrderingOfSCCs.empty()) {
        if (not isVisited[topologicalOrderingOfSCCs.top()]) {
            secondDFS(topologicalOrderingOfSCCs.top(), transposedAdjacencyList, isVisited, &toBeWritten);
            numberOfSCCs++;
            toBeWritten = toBeWritten + "\n";
        }

        topologicalOrderingOfSCCs.pop();
    }

    ofstream output("ctc.out");
    output<<numberOfSCCs<<'\n'<<toBeWritten;
}




int main() {
    int numberOfNodes, numberOfEdges, outNode, inNode;
    ifstream input("ctc.in");
    
    input>>numberOfNodes>>numberOfEdges;
    vector<int> adjacencyList[numberOfNodes];
    
    for(int i=0; i<numberOfEdges; i++) {
        input>>outNode>>inNode;
        adjacencyList[outNode-1].push_back(inNode-1);
    }

    writeSCCs(numberOfNodes, adjacencyList);
    
    return 0;
}