Cod sursa(job #3360763)

Utilizator pkseVlad Bondoc pkse Data 16 iulie 2026 12:27:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int nmax = 100'000;
bool viz[nmax];

void dfs(int node, vector<int> *adj, vector<int> &ans) {
    viz[node] = true;
    for(auto i : adj[node])
        if(!viz[i]) dfs(i, adj, ans);
    ans.pb(node);
}

vector<int> adj[nmax];
vector<int> radj[nmax];
vector<int> topo;
vector<int> ctc[nmax];

int main() {
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    int n, m; cin >> n >> m;
    topo.reserve(n);
    for(int u, v; m --;) {
        cin >> u >> v; u --; v --;
        adj[u].pb(v); radj[v].pb(u);
    }

    for(int i = 0; i < n; i ++) {
        if(!viz[i])
            dfs(i, adj, topo);
    }

    memset(viz, 0, sizeof(bool) * n);

    reverse(topo.begin(), topo.end());
    int cnt = 0;
    for(auto i : topo) {
        if(!viz[i])
            dfs(i, radj, ctc[cnt ++]);
    }

    cout << cnt << '\n';

    for(int i = 0; i < cnt; i ++) {
        sort(ctc[i].begin(), ctc[i].end());
        for(auto j : ctc[i])
            cout << j + 1 << ' ';
        cout << '\n';
    }
}