Cod sursa(job #3372342)

Utilizator maria_avramAvram Maria Teodora maria_avram Data 3 noiembrie 2026 11:35:33
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 100005;
vector<int> exit_order, ctc;
vector<vector<int>> graph, t_graph, comps;
int n, m, x, y, no_ctc;
bitset<NMAX> used;
void dfs(int node) {
    used[node] = 1;
    for (int neighbour : graph[node]) {
        if (!used[neighbour]) dfs(neighbour);
    }
    exit_order.push_back(node);
}

void dfs_t(int node)
{
    used[node] = 1;
    ctc[node] = no_ctc;
    for (int neighbour : t_graph[node])
        if (!used[neighbour])
            dfs_t(neighbour);
}

void Kosaraju() {
    for (int i = 1; i <= n; i++)
        if (!used[i])
            dfs(i);

    reverse(exit_order.begin(), exit_order.end());
    used.reset();
    ctc.resize(n + 1);

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

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

int main() {
    f >> n >> m;
    graph.resize(n + 1);
    t_graph.resize(n + 1);

    for (int i = 0; i < m; i++) {
        graph[x].push_back(y);
        t_graph[y].push_back(x);

        Kosaraju();
    }

    g << no_ctc << '\n';
    for (int i = 1; i <= no_ctc; i++)
    {
        for (int node : comps[i])
            g << node << ' ';
        g << '\n';
    }

    return 0;
}