Cod sursa(job #3206813)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 24 februarie 2024 11:01:21
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <bits/stdc++.h>

using namespace std;

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

int numberOfNodes, numberOfEdges;
vector<vector<int>> graph;
vector<bool> visited;
vector<int> index;
vector<int> lowlink;
vector<vector<int>> stronglyConnectedComponents;
stack<int> visitingStack;
int globalIndex;

void initGraphs() {
    graph = vector<vector<int>>(numberOfNodes + 1);
    visited = vector<bool>(numberOfNodes + 1, false);
    index = vector<int>(numberOfNodes + 1);
    lowlink = vector<int>(numberOfNodes + 1);
}

void readData() {
    fin >> numberOfNodes >> numberOfEdges;
    initGraphs();
    int x, y;
    while (numberOfEdges--) {
        fin >> x >> y;
        graph[x].emplace_back(y);
    }
}

void tarjan(int node) {
    visited[node] = true;
    index[node] = lowlink[node] = ++globalIndex;
    visitingStack.emplace(node);

    for (const int& neighbour: graph[node]) {
        if (!visited[neighbour]) {
            tarjan(neighbour);
            lowlink[node] = min(lowlink[node], lowlink[neighbour]);
        }
        else {
            lowlink[node] = min(lowlink[node], index[neighbour]);
        }
    }

    if (index[node] == lowlink[node]) {
        vector<int> stronglyConnectedComponent;
        int stackNode;
        do {
            stackNode = visitingStack.top();
            visitingStack.pop();
            stronglyConnectedComponent.emplace_back(stackNode);
        } while (stackNode != node);
        stronglyConnectedComponents.emplace_back(stronglyConnectedComponent);
    }
}

void computeStronglyConnectedComponents() {
    for (int node = 1; node <= numberOfNodes; ++node) {
        if (!visited[node]) {
            tarjan(node);
        }
    }
}

void printStronglyConnectedComponents() {
    fout << stronglyConnectedComponents.size() << '\n';
    for (const auto& component: stronglyConnectedComponents) {
        for (const int& node: component) {
            fout << node << ' ';
        }
        fout << '\n';
    }
}

int main()
{
    readData();
    computeStronglyConnectedComponents();
    printStronglyConnectedComponents();

    fin.close();
    fout.close();
    return 0;
}