Cod sursa(job #3271502)

Utilizator eusebiuuRimboi Eusebiu eusebiuu Data 26 ianuarie 2025 13:25:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector<vector<int>> kosaraju(int n, vector<vector<int>> graph) {
    vector<vector<int>> reversedGraph(n + 1);
    vector<bool> visited(n + 1), visitedBackwards(n + 1);
    vector<int> comp(n + 1);
    stack<int> nodes;

    for (int i = 1; i <= n; ++i) {
        for (int x : graph[i]) {
            reversedGraph[x].push_back(i);
        }
    }

    function<void(int)> dfs1 = [&](int node) {
        visited[node] = true;
        for (int dest : graph[node]) {
            if (visited[dest])
                continue;
            dfs1(dest);
        }
        nodes.push(node);
    };

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs1(i);
        }
    }

    vector<vector<int>> scc;
    vector<int> curr_scc;

    function<void(int)> dfs2 = [&](int node) {
        visitedBackwards[node] = true;
        comp[node] = scc.size();
        curr_scc.push_back(node);
        for (int dest : reversedGraph[node]) {
            if (visitedBackwards[dest])
                continue;
            dfs2(dest);
        }
    };

    while (!nodes.empty()) {
        int curr_node = nodes.top();
        nodes.pop();
        if (visitedBackwards[curr_node]) {
            continue;
        }
        dfs2(curr_node);
        scc.push_back(curr_scc);
        curr_scc.clear();
    }
    return scc;
}

int main() {
    int n, m;
    fin >> n >> m;
    vector<vector<int>> graph(n + 1);
    for (int i = 1; i <= m; ++i) {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
    }

    auto components = kosaraju(n, graph);

    fout << components.size() << '\n';
    for (auto nodes : components) {
        for (int x : nodes) {
            fout << x << ' ';
        }
        fout << '\n';
    }
    return 0;
}