Cod sursa(job #3225657)

Utilizator cristiWTCristi Tanase cristiWT Data 18 aprilie 2024 13:55:19
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int nmax = 2e5 + 5, mod = 1e9 + 7, inf = 2e18;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef LOCAL
    freopen("file.in", "r", stdin);
    freopen("file.out", "w", stdout);
#else
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
#endif

    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<vector<int>> gt(n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    vector<int> ord;
    vector<int> viz(n + 1);
    function<void(int)> dfs = [&](int x) {
        viz[x] = 1;
        for (auto y: g[x]) {
            if (!viz[y]) {
                dfs(y);
            }
        }
        ord.push_back(x);
    };
    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfs(i);
        }
    }

    reverse(ord.begin(), ord.end());
    vector<vector<int>> ans;
    vector<int> comp;
    viz = vector<int>(n + 1, 0);
    dfs = [&](int x) {
        viz[x] = 1;
        comp.push_back(x);
        for (auto y: gt[x]) {
            if (!viz[y]) {
                dfs(y);
            }
        }
    };
    for (auto i: ord) {
        if (viz[i]) continue;
        comp.clear();
        dfs(i);
        ans.push_back(comp);
    }
    cout << ans.size() << '\n';
    for (auto v: ans) {
        for (auto x: v) {
            cout << x << ' ';
        }
        cout << '\n';
    }
}