Cod sursa(job #3371160)

Utilizator vik4torTunaru Victor-Cristian vik4tor Data 28 octombrie 2026 19:52:15
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <vector>
#include <fstream>
#include <bitset>
#include <algorithm>

using namespace std;

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

vector<vector<int>> graph;
vector<vector<int>> graph_t;
vector<vector<int>> ctc;
vector<int> f;

constexpr int NMAX = 100005;
bitset<NMAX> visited;

int nr_ctc = 0;

void dfs(int nod) {
    visited[nod] = true;
    for (int next : graph[nod]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
    f.push_back(nod);
}

void dfs_t(int nod) {
    visited[nod] = true;
    ctc[nr_ctc].push_back(nod);
    for (int next : graph_t[nod]) {
        if (!visited[next]) {
            dfs_t(next);
        }
    }
}

int main() {
    int N, M, X, Y;
    fin >> N >> M;
    graph.assign(N+1, vector<int>());
    graph_t.assign(N+1, vector<int>());
    f.reserve(N);
    for (int i = 0; i < M; i++) {
        fin >> X >> Y;
        graph[X].push_back(Y);
        graph_t[Y].push_back(X);
    }
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) dfs(i);
    }
    visited.reset();
    reverse(f.begin(), f.end());
    for (int i : f) {
        if (!visited[i]) {
            ctc.emplace_back();
            dfs_t(i);
            nr_ctc++;
        }
    }
    fout << nr_ctc << '\n';
    for (int i = 0; i < nr_ctc; i++) {
        for (int nod: ctc[i])
            fout << nod << ' ';
        fout << '\n';
    }
}