Cod sursa(job #2817168)

Utilizator RoberttoPopescu Paullo Robertto Karloss Robertto Data 13 decembrie 2021 00:41:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include    <fstream>
#include    <iostream>
#include    <vector>
#include    <stack>

#define NMax 100005

using namespace std;

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

stack<int> S;

vector<int> GT[NMax], CTC[NMax];


struct muchie {
    int destinatie, cost, capacitate;

    muchie(int destinatie, int cost, int capacitate) : destinatie(destinatie), cost(cost), capacitate(capacitate) {}
};

vector<vector<muchie>> G;

int N, M, NrCTC;
int beenThere[NMax];

void Read() {
    fin >> N >> M;
    G.resize(N + 1, vector<muchie>());
    for (int i = 1; i <= M; i++) {
        int x, y, cost = 0, capacitate = 0;
        fin >> x >> y;
        G[x].push_back(muchie(y, cost, capacitate)); // Construim graful G
        GT[y].push_back(x); // Construim transpusa grafului G
    }
}

void DFSP(int Nod) {
    beenThere[Nod] = 1;
    for (auto &i: G[Nod]) {
        int Vecin = i.destinatie;

        if (!beenThere[Vecin])
            DFSP(Vecin);
    }
    S.push(Nod);
}

void DFSM(int Nod) {
    beenThere[Nod] = 2;
    CTC[NrCTC].push_back(Nod);

    for (unsigned int i = 0; i < GT[Nod].size(); i++) {
        int Vecin = GT[Nod][i];

        if (beenThere[Vecin] == 1)
            DFSM(Vecin);
    }
}

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

    while (!S.empty()) {
        int Nod = S.top();
        cout << Nod << " ";
        if (beenThere[Nod] == 1) {
            NrCTC++;
            DFSM(Nod);
        }
        S.pop();
    }
//    while(!S.empty()) {
//        fout << S.top() << " ";
//        S.pop();
//    }
}

void Print() {
    fout << NrCTC << "\n";

    for (int i = 1; i <= NrCTC; i++) {
        for (unsigned int j = 0; j < CTC[i].size(); j++)
            fout << CTC[i][j] << " ";
        fout << "\n";
    }
}

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