Cod sursa(job #2538809)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 5 februarie 2020 10:19:41
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#define DM 100001
#define inf 0x3f3f3f3f
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream fi ("echipe.in");
ofstream fo ("echipe.out");
bool ins[DM];
int n, m, a, b, idx[DM], ctc[DM], total, midx[DM], nw;
stack <int> st;
vector <int> v[DM];

void discover(int nod) {
    idx[nod] = midx[nod] = ++nw;
    ins[nod] = 1;
    st.push(nod);
    for (auto i:v[nod]) {
        if (idx[i] < idx[nod] && ins[i]) {
            midx[nod] = min(idx[i], midx[nod]);
        } else if (idx[i] == inf) {
            discover(i);
            midx[nod] = min(midx[i], midx[nod]);
        }
    }
    if (midx[nod] == idx[nod]) {
        ++total;
        while (st.top() != nod) {
            ctc[st.top()] = total;
            st.pop();
        }
        ctc[nod] = total;
        st.pop();
    }
    ins[nod] = 0;
}

int main() {
    fi >> n >> m;
    for (int i = 1; i <= n; ++i)
        idx[i] = inf;
    for (int i = 1; i <= m; ++i) {
        fi >> a >> b;
        v[a].push_back(b);
    }
    for (int i = 1; i <= n; ++i)
        if (!ctc[i])
            discover(i);
    fo << total;
    return 0;
}