Cod sursa(job #2901607)

Utilizator moltComan Calin molt Data 14 mai 2022 01:04:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100005

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

unordered_set<int> is_in_stack;
int timestamp = 0;
void dfs(vector<int> graph[NMAX], int node, bool visited[NMAX],
         int low_link[], stack<int>& st, int found[], vector<vector<int>>& sccs) {
    visited[node] = true;

    st.push(node);
    is_in_stack.insert(node);
    found[node] = ++timestamp;
    low_link[node] = found[node];

    for (auto& neigh : graph[node]) {
        if (!visited[neigh]) {
            dfs(graph, neigh, visited, low_link, st, found, sccs);
            low_link[node] = min(low_link[node], low_link[neigh]);

        } else if (is_in_stack.find(neigh) != is_in_stack.end()) {
            low_link[node] = min(low_link[node], low_link[neigh]);
        }
    }
    
    if (low_link[node] == found[node]) {
        vector<int> curr_scc;
        while (true) {
            if (st.top() == node) {
                st.pop();
                is_in_stack.erase(node);
                break;
            }
            curr_scc.push_back(st.top());
            is_in_stack.erase(st.top());
            st.pop();
        }
        curr_scc.push_back(node);
        sccs.push_back(curr_scc);
    }
}

vector<vector<int>> tarjan(vector<int> graph[NMAX], int n) {
    stack<int> st;
    bool visited[NMAX];

    int low_link[NMAX];
    int found[NMAX];

    memset(visited, 0, sizeof(visited));
    memset(low_link, 0x3f, sizeof(low_link));
    memset(found, 0x3f, sizeof(found));

    vector<vector<int>> sccs;

    for (int node = 1; node <= n; ++node) {
        if (!visited[node]) {
            dfs(graph, node, visited, low_link, st, found, sccs);
        }
    }

    return sccs;
}

int main()
{
    int n, m;
    in >> n >> m;
    vector<int> graph[NMAX];
    for (int i = 1; i <= m; ++i) {
        int x, y;
        in >> x >> y;
        graph[x].push_back(y);
    }

    vector<vector<int>> sccs = tarjan(graph, n);

    out << sccs.size() << "\n";
    for (int i = 0; i < sccs.size(); ++i) {
        for (int j = 0; j < sccs[i].size(); ++j) {
            out << sccs[i][j] << " ";
        }
        out << "\n";
    }
}