Cod sursa(job #3348417)

Utilizator tmxmatTudor Matasaru Mihai tmxmat Data 21 martie 2026 17:47:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.34 kb
#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> rev_adj[NMAX + 1];

    int n, m;

public:

    vector<vector<int>> scc;

    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])
            {
                rev_adj[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, rev_adj, component);
            }

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

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()
{
    read();
    process();
    print_result();
    return 0;
}