Cod sursa(job #3245796)

Utilizator slol003Rizea Alexandru-Gabriel slol003 Data 30 septembrie 2024 17:55:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 1;

vector<int> adj[nmax], inv[nmax], ord, comp[nmax];

int cnt = 0;

bool f[nmax];

void dfs1(int i) {
    f[i] = 1;
    for(auto it : inv[i]) {
        if(!f[it]) {
            dfs1(it);
        }
    }
    ord.push_back(i);
}

void dfs2(int i) {
    f[i] = 1;
    comp[cnt].push_back(i);
    for(auto it : adj[i]) {
        if(!f[it]) {
            dfs2(it);
        }
    }
}

int main() {
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        inv[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
        if(!f[i]) {
            dfs1(i);
        }
    }
    reverse(ord.begin(), ord.end());
    memset(f, 0, sizeof(f));
    for(auto it : ord) {
        if(!f[it]) {
            dfs2(it);
            cnt++;
        }
    }
    cout << cnt << '\n';
    for(int i = 0; i < cnt; i++) {
        // cout << comp[i].size() << " ";
        for(auto it : comp[i]) {
            cout << it << " ";
        }
        cout << '\n';
    }
    return 0;
}