Cod sursa(job #3371064)

Utilizator OmarSorinAl Daraghmeh Omar-Sorin OmarSorin Data 28 octombrie 2026 13:43:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 100005;
int n, m, no_ctc;
vector<int> exit_order, ctc;
vector<vector<int>> graph, t_graph, comps;
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 = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        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;
}