Cod sursa(job #3120402)

Utilizator Ion.AAlexandru Ion Ion.A Data 6 aprilie 2023 14:10:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>

using namespace std;

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

const int N = 1e5 + 1;
const int M = 2e5 + 1;

struct elem{
    int vf, urm;
};
elem v_s[M], v_p[M], ctc[M];
int lst_s[N], lst_p[N], lst_c[N];
int n, m, nr_s, nr_p, nr_c;
int v_s_top[N], n_s_top, c[N], n_c;
bool viz[N];

void adauga(int x, int y, elem v[], int lst[], int &nr)
{
    nr++;
    v[nr].vf = y;
    v[nr].urm = lst[x];
    lst[x] = nr;
}

void dfs_ini(int x)
{
    viz[x] = true;
    for (int p = lst_s[x]; p != 0; p = v_s[p].urm)
    {
        int y = v_s[p].vf;
        if (!viz[y])
        {
            dfs_ini(y);
        }
    }
    v_s_top[++n_s_top] = x;
}

void dfs_trans(int x)
{
    c[x] = n_c;
    for (int p = lst_p[x]; p != 0; p = v_p[p].urm)
    {
        int y = v_p[p].vf;
        if (c[y] == 0)
        {
            dfs_trans(y);
        }
    }
}

int main()
{
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        in >> x >> y;
        adauga(x, y, v_s, lst_s, nr_s);
        adauga(y, x, v_p, lst_p, nr_p);
    }
    /// I
    for (int i = 1; i <= n; i++)
    {
        if (!viz[i])
        {
            dfs_ini(i);
        }
    }
    /// II
    for (int i = n_s_top; i >= 1; i--)
    {
        if (c[v_s_top[i]] == 0)
        {
            n_c++;
            dfs_trans(v_s_top[i]);
        }
    }
    out << n_c << "\n";
    for (int i = n; i >= 1; i--)
    {
        adauga(c[i], i, ctc, lst_c, nr_c);
    }
    for (int i = 1; i <= n_c; i++)
    {
        for (int p = lst_c[i]; p != 0; p = ctc[p].urm)
        {
            int x = ctc[p].vf;
            out << x << " ";
        }
        out << "\n";
    }
    return 0;
}