Cod sursa(job #3042218)

Utilizator RalucaioneteRalucaIonete Ralucaionete Data 4 aprilie 2023 20:02:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <fstream>
using namespace std;

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

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

struct element
{
    int vf, urm;
};

element v_s[M+1], v_p[M+1], ctc[N+1];
int lst_s[N+1], lst_p[N+1], lst_c[N+1];
int n, m, nr_s, nr_p, nr_c;
int v_s_top[N+1], n_s_top, c[N+1], n_c;
bool viz[N+1];

void adauga(int x, int y, element 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] = 1;
    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()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        adauga(x, y, v_s, lst_s, nr_s);
        adauga(y, x, v_p, lst_p, nr_p);
    }
    ///pasul 1
    for (int i = 1; i <= n; i++)
    {
        if (!viz[i])
        {
            dfs_ini(i);
        }
    }
    ///pasul 2
    for (int i = n_s_top; i >= 1; i--)
    {
        if (c[v_s_top[i]] == 0)
        {
            n_c++;
            dfs_trans(v_s_top[i]);
        }
    }
    cout << n_c << "\n";
    for (int i = n; i >= 1; i--)
    {
        adauga(c[i], i, ctc, lst_c, nr_c);///il adaug pe i in lista c[i]
    }
    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;
            cout << x << " ";
        }
        cout << "\n";
    }

    return 0;
}