Cod sursa(job #3359865)

Utilizator Dani111Gheorghe Daniel Dani111 Data 5 iulie 2026 16:58:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
 
    int N, M;
    cin >> N >> M;
    vector<vector<int>>G(N + 3), Gt(N + 3);
    vector<int>count(N + 3);
    for(int i = 0; i < M; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        Gt[y].push_back(x);

    }
    vector<int>v(N + 3);
    vector<int>ord;
    auto dfs = [&] (int nod, auto self) -> void{
        v[nod] = 1;
        for(auto i : G[nod]) {
            if(!v[i]) {
                self(i, self);
            }
        }
        ord.push_back(nod);
    };

    for(int i = 1; i <= N; i++) {
        if(!v[i]) {
            dfs(i, dfs);
        }
    }
    vector<int>v1(N + 3);
    vector<vector<int>>ctc;
    auto dfs1 = [&] (int nod, auto self, vector<int>&ans) -> void{
        v1[nod] = 1;
        ans.push_back(nod);
        for(auto i : Gt[nod]) {
            if(!v1[i]) {
                self(i, self, ans);
            }
        }
    };
    reverse(ord.begin(), ord.end());
    for(auto i : ord) {
        if(!v1[i]) {
            vector<int>ans;
            dfs1(i, dfs1, ans);
            ctc.push_back(ans);
        }
    }
    cout << ctc.size() << '\n';
    for(auto i : ctc) { 
        for(auto j : i) {
            cout << j << ' ';
        }
        cout << '\n';
    }

}