Cod sursa(job #2713858)

Utilizator vnedelcuVictor Andrei Nedelcu vnedelcu Data 28 februarie 2021 19:35:39
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.83 kb
#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

class Tarjan {
private:
    int no_nodes;
    vector<vector<int> > graph;
    stack<int> stack;
    vector<int> node_discovery_time;
    vector<int> component_discovery_time;
    vector<bool> in_stack;
    int time;
    int total_components;
    vector<vector<int> > components;

    void tarjan(int node);
public:
    Tarjan(vector<vector<int> > & graph);
    vector<vector<int> > get_components();
    int get_no_components() {return total_components;}
};

Tarjan::Tarjan(vector<vector<int> > & graph) {
    no_nodes = graph.size();
    this->graph = graph;
    node_discovery_time.resize(no_nodes, 0);
    component_discovery_time.resize(no_nodes, 0);
    in_stack.resize(no_nodes, false);
    time = 1;
    total_components = 0;
    components.resize(no_nodes);
}

void Tarjan::tarjan(int node) {
    node_discovery_time[node] = time;
    component_discovery_time[node] = time;
    ++time;
    stack.push(node);
    in_stack[node] = true;

    for (int neighbor: graph[node]) {
        if (!node_discovery_time[neighbor]) {
            tarjan(neighbor);
            component_discovery_time[node] =
                min(component_discovery_time[node], component_discovery_time[neighbor]);
        } else if (in_stack[neighbor]) {
            component_discovery_time[node] =
                min(component_discovery_time[node], component_discovery_time[neighbor]);
        }
    }

    if (node_discovery_time[node] == component_discovery_time[node]) {
        while (stack.top() != node) {
            components[total_components].push_back(stack.top());
            in_stack[stack.top()] = false;
            stack.pop();
        }
        components[total_components].push_back(stack.top());
        in_stack[stack.top()] = false;
        stack.pop();
        ++total_components;
    }
}

vector<vector<int> > Tarjan::get_components() {
    for (int i = 0; i < no_nodes; ++i) {
        if (!node_discovery_time[i]) {
            tarjan(i);
        }
    }
    return components;
}

int main() {
    FILE * f;
    int n, m, x, y;

    f = fopen("ctc.in", "r");
    fscanf(f, "%d%d", &n, &m);
    vector<vector<int> > graph(n);
    for (int i = 0; i < m; ++i) {
        fscanf(f, "%d%d", &x, &y);
        --x;
        --y;
        graph[x].push_back(y);
    }
    fclose(f);

    Tarjan tarjan(graph);
    vector<vector<int> > components = tarjan.get_components();

    f = fopen("ctc.out", "w");
    fprintf(f, "%d\n", tarjan.get_no_components());
    for (int i = 0; i < n; ++i) {
        if (!components[i].size()) {
            continue;
        }
        for (int node: components[i]) {
            fprintf(f, "%d ", node + 1);
        }
        fprintf(f, "\n");
    }
    fclose(f);

    return 0;
}