Cod sursa(job #3348418)

Utilizator tmxmatTudor Matasaru Mihai tmxmat Data 21 martie 2026 18:19:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3 kb
#pragma GCC optimize("Ofast")

#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int NMAX = 100000;
const int MMAX = 200000;

class Graph
{
private:

    bool visited[NMAX + 1];

    vector<int> adj[NMAX + 1];
    vector<int> adj_rev[NMAX + 1];

    int n, m;

public:

    vector<vector<int>> scc;
    vector<vector<int>> adj_compact;

    int roots[NMAX + 1];

    void init(int n, int m)
    {
        this->n = n;
        this->m = m;
    }

    void add_dir_edge(int src, int dest)
    {
        adj[src].push_back(dest);
    }

    void reverse_edges()
    {
        for (int i = 1; i <= n; i ++)
        {
            for (int u : adj[i])
            {
                adj_rev[u].push_back(i);
            }
        }
    }

    void dfs(int nod, vector<int> adja[], vector<int> &output)
    {
        visited[nod] = 1;

        for (auto u : adja[nod])
        {
            if (!visited[u])
            {
                dfs(u, adja, output);
            }
        }

        output.push_back(nod);
    }

    void reset_visited()
    {
        memset(visited, 0, sizeof(visited));
    }

    void get_scc_kosaraju()
    {
        vector<int> order;
        reset_visited();
        for (int i = 1; i <= n; i ++)
        {
            if (!visited[i])
            {
                dfs(i, adj, order);
            }
        }

        reverse_edges();

        reset_visited();
        for (int i = n - 1; i >= 0; i --)
        {
            int ind = order[i];
            vector<int> component;

            if (!visited[ind])
            {
                dfs(ind, adj_rev, component);
            }

            if (!component.empty())
            {
                scc.push_back(component);

                int root = *component.begin();
                for (auto u : component)
                {
                    roots[u] = root;
                }
            }
        }

        adj_compact.assign(n, {});
        for (int nod = 1; nod <= n; nod ++)
        {
            for (auto u : adj[nod])
            {
                if (roots[nod] != roots[u])
                {
                    adj_compact[roots[nod]].push_back(roots[u]);
                }
            }
        }
    }
};

int n, m;

Graph g;

void read()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i ++)
    {
        int a, b;
        cin >> a >> b;

        g.add_dir_edge(a, b);
    }
}

void process()
{
    g.init(n, m);
    g.get_scc_kosaraju();
}

void print_result()
{
    cout << g.scc.size() << "\n";

    for (auto nodes : g.scc)
    {
        for (auto nod : nodes)
        {
            cout << nod << " ";
        }
        cout << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    process();
    print_result();
    return 0;
}