Cod sursa(job #3248750)

Utilizator vladm98Munteanu Vlad vladm98 Data 13 octombrie 2024 00:30:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> graph[200005], revGraph[200005];
vector <int> depOrder;
vector <int> components[200005];
int component[200005], sizes[200005];
bool visitedOrder[200005], visitedComponents[200005];

// Build an order of node such that IF there is a path from X to Y, then Y will be before X in the order
// This order is later on reversed so that X will be before Y
void buildOrder(int node) {
    visitedOrder[node] = true;

    for (auto x : graph[node]) {
        if (visitedOrder[x]) continue;
        buildOrder(x);
    }

    depOrder.emplace_back(node);
}

// Build the components based on the order that was generated. We know from the order that if I can only reach
// from X to Y (and not from Y to X), X will be computed first. Therefore, by the time we compute Y, X will already be
// visited. If we reach Y coming from X on the reversed graph, that means that X is reachable from Y on the initial graph.
// Moreover, if Y is not already visited, it means that Y is after X in the order of nodes, so Y must also be reachable
// from X on the initial graph. Therefore, X and Y are in the same strongly connected component.
void buildComponents(int node, int currentComponent) {
    visitedComponents[node] = true;

    for (auto x : revGraph[node]) {
        if (visitedComponents[x]) continue;
        buildComponents(x, currentComponent);
    }

    components[currentComponent].emplace_back(node);
    sizes[currentComponent] += 1;
    component[node] = currentComponent;
}

set <int> componentsGraph[200005];
vector <pair <int, int>> edges;

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        edges.emplace_back(x, y);
        graph[x].emplace_back(y);
        revGraph[y].emplace_back(x);
    }
    for (int i = 1; i <= n; ++i) {
        if (visitedOrder[i]) continue;
        buildOrder(i);
    }
    reverse(depOrder.begin(), depOrder.end());
    int nComponents = 0;
    for (auto node : depOrder) {
        if (visitedComponents[node]) continue;
        nComponents += 1;
        buildComponents(node, nComponents);
    }

    for (auto edge : edges) {
        if (component[edge.first] == component[edge.second]) continue;
        componentsGraph[component[edge.first]].insert(component[edge.second]);
    }

    cout << nComponents << '\n';
    for (int i = 1; i <= nComponents; ++i) {
        for (auto node : components[i]) {
            cout << node << ' ';
        }
        cout << '\n';
    }
    return 0;
}