Cod sursa(job #3303201)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 14 iulie 2025 18:28:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;
const int NMAX = 100002;

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

bitset <NMAX> f;
vector <vector <int>> v, inv, ctc;
vector <int> topo;

void dfs(int start, vector <vector <int>>& adj, vector <int>& add_to) {
    f[start] = 1;
    for(auto nod : adj[start]) {
        if(!f[nod])
            dfs(nod, adj, add_to);
    }
    add_to.push_back(start);
}


int main() {
    int n, m;
    cin >> n >> m;
    v.resize(n + 1);
    inv.resize(n + 1);
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        inv[b].push_back(a);
    }
    f = 0;
    for(int i = 1; i <= n; i++) {
        if(!f[i])
            dfs(i, v, topo);
    }
    /*cout << "mergee\n";
    for(int i = 0; i < topo.size(); i++)
        cout << topo[i] << " ";
    cout << '\n';*/

    f = 0;
    for(int i = topo.size() - 1; i >= 0; i--) {
        if(!f[topo[i]]) {
            ctc.push_back(vector <int>());
            dfs(topo[i], inv, ctc.back());
        }
    }
    cout << ctc.size() << '\n';
    for(int i = 0; i < ctc.size(); i++) {
        for(const int& x : ctc[i])
            cout << x << " ";
        cout << '\n';
    }
    return 0;
}