Cod sursa(job #3303674)

Utilizator vvalentinCiun Valentin vvalentin Data 17 iulie 2025 10:17:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

const int NMAX = 1e5;
int n, m, x, y, num_comp;

bool vis[NMAX + 2];
int comp[NMAX + 2];
vector<int> G[NMAX + 2], Gt[NMAX + 2];
vector<int> S;


void dfs(int node, vector<int> G[], int curr_comp) {
    comp[node] = curr_comp;
    for (auto nxt : G[node]) {
        if (!comp[nxt]) {
            dfs(nxt, G, curr_comp);
        }
    }
}

void sort_top (int node) {
    vis[node] = true;
    for (auto nxt : G[node]) {
        if (!vis[nxt]) {
            sort_top(nxt);
        }
    }
    S.push_back(node);
}

int main() {
    fin >> n >> m;
    while (m--) {
        fin >> x >> y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            sort_top(i);
        }
    }

    reverse(S.begin(), S.end());
    memset(vis, 0, sizeof(vis));

    for (auto x : S) {
        if (!comp[x]) {
            dfs(x, Gt, ++num_comp);
        }
    }

    vector<vector<int>> comps(num_comp);
    for (int i = 1; i <= n; i++) {
        comps[comp[i] - 1].push_back(i);
    }

    fout << num_comp << '\n';
    for (auto component : comps) {
        for (auto node : component) {
            fout << node << ' ';
        }
        fout << '\n';
    }

    return 0;
}