Cod sursa(job #3041005)

Utilizator SergetecLefter Sergiu Sergetec Data 30 martie 2023 19:32:39
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
/*
 * Lefter Sergiu - 30/03/2023
*/
#include <fstream>

using namespace std;

ifstream in("ctc.in");
ofstream out("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) { //pe initial
    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) { //pe transpus
    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 = 1; 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);
    }
    //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]);
        }
    }
    out << n_c << '\n';
    //Pasul 3
    for (int i = n; i >= 1; ++i) { //listele sunt organizate ca stivele si atunci trebuie adaugate in ordine inversa
        adauga(c[i], i, ctc, lst_c, nr_c); //il adaug pe i in lista c[i] | adica imi fac o lista cu fiecare componenta
    }
    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';
    }
    in.close();
    out.close();
    return 0;
}