Pagini recente » Cod sursa (job #1345066) | Cod sursa (job #1938252) | Cod sursa (job #1038375) | Cod sursa (job #917881) | Cod sursa (job #3041005)
/*
* 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;
}