Cod sursa(job #3304324)

Utilizator vladm98Munteanu Vlad vladm98 Data 22 iulie 2025 15:26:07
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> graph[100005];
int visited[100005];

void builtTopoSort(int node, vector <int> &topoSort) {
    visited[node] = 1;
    for (auto x : graph[node]) {
        if (!visited[x]) {
            builtTopoSort(x, topoSort);
        }
    }
    topoSort.push_back(node);
}

void buildCtc(int node, vector <int> &ctc) {
    visited[node] = 0;
    ctc.push_back(node);
    for (auto x : graph[node]) {
        if (visited[x]) {
            buildCtc(x, ctc);
        }
    }
}

int main(){
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
    }
    vector <int> topoSort;

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

    vector <vector <int>> ctcs;

    for (auto node : topoSort) {
        if (visited[node]) {
            ctcs.push_back(vector <int>());
            buildCtc(node, ctcs.back());
        }
    }

    cout << ctcs.size() << '\n';
    for (auto x : ctcs) {
        for (auto y : x) {
            cout << y << ' ';
        }
        cout << '\n';
    }

    return 0;
}