Cod sursa(job #3374218)

Utilizator badiumihneaBadiu Mihnea badiumihnea Data 8 noiembrie 2026 20:46:08
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
std::vector<std::vector<int>> graph, t_graph, comps;
std::vector<int> exit_order, ctc;
int nr_ctc, n, m;
std::bitset<100001> visited;

void dfs(int node) {
    visited[node] = 1;
    for (int next:graph[node]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
    exit_order.push_back(node);
}

void dfs_t(int node) {
    visited[node] = 1;
    ctc[node] = nr_ctc;
    for (int next : t_graph[node]) {
        if (!visited[next]) {
            dfs_t(next);
        }
    }
}

void Kosaraju() {
    for (int i =1; i<=n; i++) {
        if (visited[i]) {
            dfs(i);
        }
    }
    reverse(exit_order.begin(), exit_order.end());
    visited.reset();
    ctc.resize(n+1);

    for (int node : exit_order) {
        if (!visited[node]) {
            nr_ctc++;
            dfs_t(node);
        }
    }

    comps.resize(nr_ctc + 1);
    for (int i=1; i<=n; i++) {
        comps[ctc[i]].push_back(i);
    }
}

int main() {
    int x,y;
    fin>>n>>m;
    graph.resize(n+1);
    t_graph.resize(n+1);

    for (int i=1; i<=m; i++) {
        fin>>x>>y;
        graph[x].push_back(y);
        t_graph[y].push_back(x);
    }
    Kosaraju();
    fout<<nr_ctc<<"\n";
    for (int i =1; i<=nr_ctc; i++) {
        for (int node : comps[i]) {
            fout<<node<<" ";
        }
        fout<<"\n";
    }
    return 0;
}