Cod sursa(job #3226804)

Utilizator RatebaSerbanescu Andrei Victor Rateba Data 22 aprilie 2024 20:30:53
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
// https://www.infoarena.ro/problema/ctc

#include <fstream>
#include <vector>

using namespace std;

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

const int MAX_N = 100005;

struct t_coada {
    int elems[MAX_N];
    int idx;
};

void init_coada(t_coada& coada) {
    coada.idx = -1;
}

void push_coada(t_coada& coada, int val) {
    coada.elems[++coada.idx] = val;
}

int pop_coada(t_coada& coada) {
    coada.idx--;
    return coada.elems[coada.idx + 1];
}

bool is_empty_coada(t_coada& coada) {
    return coada.idx == -1;
}

void dfs_coada(int nod, vector<int> graf[], bool viz[], t_coada& coada) {

    viz[nod] = true;
    push_coada(coada, nod);

    for (int i = 0; i < graf[nod].size(); i++) {
        int vecin = graf[nod][i];

        if (!viz[vecin]) {
            dfs_coada(vecin, graf, viz, coada);
        }
    }

}

void dfs_transpus(int nod, vector<int> graf[], bool viz[]) {
    viz[nod] = true;

    for (int i = 0; i < graf[nod].size(); i++) {
        int vecin = graf[nod][i];

        if (!viz[vecin]) {
            dfs_transpus(vecin, graf, viz);
        }
    }
}

int main() {

    int n, m;
    vector<int> graf[MAX_N];
    vector<int> graf_tran[MAX_N];
    bool viz[MAX_N] = {0};

    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int nod1, nod2;
        fin >> nod1 >> nod2;
        graf[nod1].push_back(nod2);
        graf_tran[nod2].push_back(nod1);
    }

    t_coada coada;
    init_coada(coada);

    for (int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfs_coada(1, graf, viz, coada);
        }
    }



    for (int i = 1; i <= n; i++) {
        viz[i] = false;
    }

    int cnt = 0;
    while (!is_empty_coada(coada)) {
        int nod = pop_coada(coada);
        // fout << nod << endl;

        if (!viz[nod]) {
            cnt++;
            dfs_transpus(nod, graf_tran, viz);
        }
    }

    fout << cnt;

    return 0;
}