N3P4 - Correo Central (Floyd Warshall)

#include <bits/stdc++.h>

using namespace std;

bool M[1001][1001];

int correocentral(int n, vector <int> a, vector <int> b)
{
    /**
    Solución que apunta a subtareas 1, 2, 3
    solo en caso que la respuesta sea n
    80% de 90 puntos = 72 puntos

    Complejidad: O(n^3) =~ 1.000.000.000
    Aunque es rápido debido a operaciones super ligeras (or, and)
    **/

    for(int i=0; i<a.size(); i++)
        M[a[i]][b[i]] = true;

    for(int i=1; i<=n; i++)
        M[i][i] = true;

    ///Algoritmo Floyd-Warshall
    ///para calcular alcanzabilidad
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                M[i][j] = M[i][j] or (M[i][k] and M[k][j]);

    bool todosUnos = true;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(M[i][j] == false)
                todosUnos = false;

    if(todosUnos)
        return n;
    return 0;
}

/**
//Función main auxiliar para testear
int main()
{
    int n, m;
    cin >> n >> m;

    vector <int> a(m), b(m);

    for(int i=0; i<m; i++)
        cin >> a[i] >> b[i];

    cout << correocentral(n, a, b) << endl;

    return 0;
}
**/