Cod sursa(job #3125966)

Utilizator seby_me14Ilinca Sebastian-Ionut seby_me14 Data 4 mai 2023 22:31:12
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>

#define NMAX 200000
#define INF (1 << 30)

using namespace std;

void dfs(int parent[NMAX], int n, int node, vector<int> adj[NMAX],
    stack<int> &st, int found[NMAX], int low_link[NMAX], int &timestamp,
    int &how_many, vector<stack<int> *> &stacks, unordered_map<int, int> map) {
    found[node] = ++timestamp;
    low_link[node] = found[node];
    st.push(node);
    map.insert({node, 1});
    for (int i = 0; i < adj[node].size(); ++i) {
        int neigh = adj[node][i];
        if (parent[neigh] != 0) {
            if (map.find(neigh) != map.end()) {
                low_link[node] = min(low_link[node], found[neigh]);
            }
            continue;
        }
        parent[neigh] = node;
        dfs(parent, n, neigh, adj, st, found, low_link, timestamp, how_many, stacks, map);

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

    if (low_link[node] == found[node]) {
        stack<int> *new_st = new stack<int>;
        int x;
        do {
            x = st.top();
            st.pop();
            map.erase(x);
            new_st->push(x);
        } while (x != node && st.size() > 0);

        stacks.push_back(new_st);
        how_many++;
    }
}

int
main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    vector<int> adj[n + 1];
    int nod1, nod2;
    for (int i = 0; i < m; ++i) {
        cin >> nod1 >> nod2;
        adj[nod1].push_back(nod2);
    }
    int parent[n + 1];
    int found[n + 1];
    int low_link[n + 1];
    for (int i = 1; i <= n; ++i) {
        parent[i] = 0;
        found[i]= INF;
        low_link[i] = INF;
    }
    stack<int> st;
    int timestamp = 0;
    int count = 0;
    vector<stack<int>*> stacks;
    unordered_map<int, int> map;
    for (int i = 1; i <= n; ++i) {
        if (parent[i] == 0) {
            parent[i] = i;
            dfs(parent, n, i, adj, st, found, low_link, timestamp, count, stacks, map);
        }
    }
    cout << count << "\n";
    for (int i = 0; i < stacks.size(); ++i) {
        stack<int> *stack = stacks[i];
        while (!stack->empty()) {
            cout << stack->top() << " ";
        }
        cout << "\n";
        delete stack;
    }
    return 0;
}