Cod sursa(job #2896795)

Utilizator mihnea.tTudor Mihnea mihnea.t Data 30 aprilie 2022 20:16:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <bits/stdc++.h>

#define INF ((int)1e9)
#define NMAX ((int)1e5)

using namespace std;

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

int n, m;
vector<int> adj[NMAX + 1];
vector<vector<int>> all_sccs;

void dfs(int node, vector<int> &parent, int &timestamp, vector<int> &found,
            vector<int> &low_link, unordered_set<int> &nodes_set, stack<int> &nodes_stack) {
        found[node] = ++timestamp;
        low_link[node] = found[node];
        nodes_set.insert(node);
        nodes_stack.push(node);

        for (auto it = adj[node].begin(); it != adj[node].end(); ++it) {
            int next_node = *it;
            if (parent[next_node] != -1) {
                if (nodes_set.find(next_node) != nodes_set.end()) {
                    low_link[node] = min(low_link[node], found[next_node]);
                }

                continue;
            }

            parent[next_node] = node;

            dfs(next_node, parent, timestamp, found, low_link, nodes_set, nodes_stack);

            low_link[node] = min(low_link[node], low_link[next_node]);
        }

        if (low_link[node] == found[node]) {
            vector<int> new_scc;

            int x;
            do {
                x = nodes_stack.top();
                nodes_stack.pop();
                nodes_set.erase(x);
                new_scc.push_back(x);
            } while (x != node);

            all_sccs.push_back(new_scc);
        }
    }

    void tarjan_scc(vector<int> &parent, vector<int> &found, vector<int> &low_link) {
        for (int i = 0; i <= n; ++i) {
            parent[i] = -1;
            found[i] = INF;
            low_link[i] = INF;
        }

        unordered_set<int> nodes_set;
        stack<int> nodes_stack;

        int timestamp = 0;
        for (int i = 1; i <= n; ++i) {
            if (parent[i] == -1) {
                parent[i] = i;

                dfs(i, parent, timestamp, found, low_link, nodes_set, nodes_stack);
            }
        }
    }

int main(void) {
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int src, dest;
        fin >> src >> dest;

        adj[src].push_back(dest);
    }
    
    vector<int> parent(n + 1);
    vector<int> found(n + 1);
    vector<int> low_link(n + 1);

    tarjan_scc(parent, found, low_link);

    fout << all_sccs.size() << "\n";
    for (size_t i = 0; i < all_sccs.size(); ++i) {
        for (size_t j = 0; j < all_sccs[i].size(); ++j) {
            fout << all_sccs[i][j] << " ";
        }

        fout << "\n";
    }

    return 0;
}