Cod sursa(job #2481877)

Utilizator Dragos1226Dragos Chileban Dragos1226 Data 27 octombrie 2019 15:25:20
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMax = 100000;
vector <int> G[NMax+5];
vector <int> T[NMax+5];
vector <int> Sol[NMax+5];
int N, M, Use[NMax+5], CTC, k, Topo[NMax+5];

void Read() {
    in >> N >> M;
    for (int i = 0, x, y; i < M; i++) {
        in >> x >> y;
        G[x].push_back(y);
        T[y].push_back(x);
    }
}

void DFSG(int Nod) {
    Use[Nod] = 1;

    for (auto Vecin : G[Nod]) {
        if(!Use[Vecin])
            DFSG(Vecin);
    }

    Topo[++k] = Nod;
}

void DFST(int Nod) {
    Use[Nod] = 2;Sol[CTC].push_back(Nod);

    for (auto Vecin : T[Nod]) {
        if(Use[Vecin] == 1)
            DFST(Vecin);
    }
}

void Solve() {
    for (int i = 1; i <= N; i++)
        if (!Use[i])
            DFSG(i);

    for (int i = k; i >= 1; i--) {
        int Nod = Topo[i];

        if(Use[Nod] == 1) {
            CTC++;
            DFST(Nod);
        }
    }
}

void Print() {
    out << CTC << '\n';
    for (int i = 1; i <= CTC; i++) {
        for (int j = 0; j < Sol[i].size(); j++)
            out << Sol[i][j] << " ";
        out << '\n';
    }
}

int main() {
    Read();
    Solve();
    Print();
}