Cod sursa(job #3327695)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 4 decembrie 2025 19:45:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
 
using namespace std;

const int N_MAX = 100000;

int N, M;
vector<int> G[N_MAX + 5];
vector<int> Gt[N_MAX + 5];
vector<int> S;
bool vis[N_MAX + 5];

void top_sort(int node) {
    vis[node] = true;
    for(auto it : G[node]) {
        if(!vis[it]) {
            top_sort(it);
        }
    }
    S.push_back(node);
}

void DFS(int node, vector<int> &x) {
    x.push_back(node);
    vis[node] = true;
    for(auto it : Gt[node]) {
        if(!vis[it]) {
            DFS(it, x);
        }
    }
}

int main() {
#ifndef LOCAL
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }

    for(int i = 1; i <= N; i++) {
        if(!vis[i]) {
            top_sort(i);
        }
    }
    reverse(S.begin(), S.end());

    fill(vis, vis + N + 1, false);
    vector<vector<int>> ctc;
    for(auto node : S) {
        cerr << node << " ";
        if(!vis[node]) {
            ctc.push_back(vector<int>());
            DFS(node, ctc.back());
        }
    }

    cout << ctc.size() << "\n";
    for(auto &c : ctc) {
        for(auto node : c) {
            cout << node << " ";
        }
        cout << "\n";
    }
    return 0;
}