N3P4 - Correo Central (múltiples DFS)

#include <bits/stdc++.h>

using namespace std;

bool M[1001][1001];
vector <vector <int> > ady;

void DFS(const int &origen, int nodo)
{
    M[origen][nodo] = true;

    for(const auto i:ady[nodo])
        if(M[origen][i] == false)
            DFS(origen, i);
}

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*DFS) = O(n*(n+m)) =~ 201.000.000
    **/

    ady = vector <vector <int> > (n+1);

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

    for(int i=1; i<=n; i++)
        DFS(i, i);

    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;
}
**/