Cod sursa(job #3124210)

Utilizator Bogdy_PPrunescu Bogdan Bogdy_P Data 27 aprilie 2023 11:29:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[100005];
int n, m;

int parent[100005];
int timestamp = 0;
int found[100005];
int low_link[100005];
stack<int> visiting_stack;
bool is_in_stack[100005];
vector<vector<int>> all_sccs;
vector<int> scc;

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

void DFS(int node) {
    found[node] = ++timestamp;
    low_link[node] = timestamp;
    visiting_stack.push(node);
    is_in_stack[node] = true;

    for (auto neigh : adj[node]) {
        if (parent[neigh] != 0) {
            if (is_in_stack[neigh])
                low_link[node] = min(low_link[node], low_link[neigh]);
        } else {

            parent[neigh] = node;
            DFS(neigh);

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

    if (found[node] == low_link[node]) {
        scc.clear();

        int x;
        do {
            x = visiting_stack.top();
            visiting_stack.pop();
            is_in_stack[x] = false;
            scc.push_back(x);
        } while (x != node);

        all_sccs.push_back(scc);
    }
}

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

    for (int i = 1; i <= n; i++)
        low_link[i] = 1e9;

    for (int i = 1; i <= n; i++) {
            if (parent[i] == 0) {
                parent[i] = i;
                DFS(i);
            }
        }
    
    out << all_sccs.size() << '\n';
    for (auto scc : all_sccs) {
        for (auto node : scc) {
            out << node << ' ';
        }
        out << '\n';
    }
}