Parece correcto mirando el código por encima y probando algunos casos. La idea era ver que el problema se puede convertir en un grafo donde los animales son los nodos y las relaciones entre ellos las aristas. Una vez hecho esto, la cuestión era ver si este grafo era bipartido o no (si se pueden partir los nodos en dos grupos tal que cada grupo no tenga aristas entre ellos, que serán los machos y las hembras).

Es fácil de demostrar y ver que si G = (V,E) es un grafo no dirigido, los siguientes enunciados son equivalentes:

1) G es bipartido.
2) G es bicoloreable (2-coloreable).
3) G no contiene ningún ciclo simple de longitud impar.

Como las tres son equivalentes, se puede mirar cualquiera de ellas y la más eficiente de comprobar es la segunda, que mirando tú código supongo que es lo que haces.

Os dejo también la solución que había preparado:

#include <iostream>
#include <vector>
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
 
bool bicolor(int u, int c, VVI& G, VI& color) {
    bool res = true;
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if (color[v] < 0) {
            color[v] = c;
            res &= bicolor(v, 1 - c, G, color);
        }
        else if (color[v] != c) res = false;
    }
    return res;
}
 
int main() {
    int n, m;
    cin >> n >> m;
    VVI G(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    VI color(n, -1);
    bool res = true;
    for (int i = 0; i < n; ++i) { //Por si hay mas de un componente
        if (color[i] < 0) {
            color[i] = 0;
            res &= bicolor(i, 1, G, color);
        }
    }
    if (res) cout << "Si" << endl;
    else cout << "No" << endl;    
}

PD: Cuidado con las salidas, tu código imprime SI y NO en vez de Si y No. A mí me da igual, pero si eres olímpico como supongo por tu firma, ves con cuidado con estas cosas en los concursos, puesto que el juez automático te daría un WA y estos errores tontos en pleno concurso pueden costar de encontrar, pensando que es problema en el código o el razonamiento.

Edito: Se me olvidaba, dos cosas:
- Para saber si un grafo es bicoloreable basta con ir asignando a cada nodo libre un color cualquiera y a sus vecinos el contrario. Si se encuentra algún vecino con el mismo color es que no es bicoloreable.

- Pon el siguiente reto xDD

Supongo que sería así:

#include <iostream>
#include <vector>
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
 
const int INF = 1000000000;
 
int dp(int n, int m, VVI& M) {
    if (n < m) return dp(m, n, M);
    if (m == 0) return 0;
    if (M[n][m] == -1) {
        M[n][m] = INF;
        for (int x = 0; x <= m; ++x) {
            M[n][m] = min(M[n][m], 1 + dp(x, m - x, M) + dp(n - x, m, M));
            M[n][m] = min(M[n][m], 1 + dp(n, m - x, M) + dp(n - x, x, M));
        }
    }
    return M[n][m];
}
 
int main() {
    int n, m;
    cin >> n >> m;
    if (n < m) swap(n, m);
    VVI M(n + 1, VI(m + 1, -1));
    cout << dp(n, m, M) << endl;
}
 

A ver si la gente le pierde un poco el miedo a las dinámicas!

Reto #10
Una compañía de autobuses sospecha que en una de sus rutas el autobús va demasiado lleno y están estudiando poner otro más para mejorar el servicio. Para ello, han colocado un contador en las puertas que registra en cada parada cuánto varía la cantidad de personas en el bus (este número podrá ser obviamente negativo).

En un cierto momento de la ruta, el conductor activa el contador y se generan los registros y más tarde lo apaga (nótese que esto implica que la suma de las diferencias podrá ser negativa, puesto que podía haber gente dentro del bus). La compañía estudiará después las sumas de subsecuencias consecutivas de la secuencia de registros. Por ejemplo, si la secuencia es -20 -15 30 -15 30, subsecuencias consecutivas son entre otras -15 30, 30 o incluso la propia secuencia completa.

Entrada:
Un número N <= 1000 en una línea. En la siguiente línea, N números indicando registros. Se cumple que los números de los registros serán menores en valor absoluto que 100.

Salida:
Escribe la mayor suma que pueda obtenerse de una subsecuencia consecutiva.

Ejemplos:

Entrada 1:

Salida 1:

Entrada 2:

Salida 2:

Notas:
- El hecho de que la N pueda ser hasta 1000 implica que una solución trivial de complejidad O(N³) no sirve (es decir, para cada posible inicio y posible final [dos fors anidados], hacer un for más anidado para calcular la suma y quedarse con la mayor). Si alguien no tiene claro si su solución es suficiente rápida (teniendo claro al menos que es correcta), se puede generar 1000 números enteros y ver cómo de rápido es su código. Debería tardar menos de un segundo, si tarda más que eso, el algoritmo no es suficiente bueno (no consiste en optimizar el código).

- Espero una solución de complejidad O(N²) intencionadamente para intentar que el problema sea más sencillo. Este problema se puede solucionar de forma más eficiente, usando una estrategia Divide&Conquer que deja una complejidad de O(NlogN) o incluso una forma ingeniosa para obtener un algoritmo O(N). Si alguien hace algún algoritmo mejor que cuadrático, como los que comento, obviamente el código será correcto.

No es la solución cuadrática estándar pero también es cuadrática y correcta, por lo tanto perfecta. En tu solución usas programación dinámica por lo que veo para calcular sec(i,j), que representa la suma de i + 1 elementos acabando en j si lo he entendido bien.

La solución cuadrática estándar usa un solo vector que guarda las sumas acumuladas, dejo el código:

#include <vector>
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> suma(n);
    for (int i = 0; i < n; ++i) {
        cin >> suma[i];
        if (i > 0) suma[i] += suma[i - 1];
    }
    //suma[i] contiene la suma de los i + 1 primeros numeros
    int res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            //Calculamos la suma de cada intervalo aprovechando el vector de sumas calculadas
            //La suma de [i,j] sera suma[j] - suma[i - 1]
            int temp = suma[j];
            if (i > 0) temp -= suma[i - 1];
            res = max(res, temp);
        }
    }
    cout << res << endl;
}
 

La solución lineal que comenté, es decir, O(N), además no requiere espacio en memoria extra. Aunque el código es muy simple, la idea puede costar un poco más de ver, pero si alguien se lo mira con invariantes puede ver que es correcto.

#include <vector>
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a, res = 0, suma = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        suma += a;
        if (suma < 0) suma = 0;
        res = max(res, suma);
    }
    cout << res << endl;
}

Pon el siguiente reto cuando quieras.

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
 
int arrf[8] = {-1,-1,-1,0,1,1,1,0};
int arrc[8] = {-1,0,1,1,1,0,-1,-1};
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char> > S(n, vector<char>(m));
    srand(time(NULL));
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < m; ++j) 
            S[i][j] = 'a' + rand()%26;
    string s;
    cin >> s;
    bool busca = true;
    for (int i = 0; i < n and busca; ++i)
        for (int j = 0; j < m and busca; ++j)
            for (int d = 0; d < 8 and busca; ++d) {
                bool ok = true;
                for (int k = 0; k < s.size() and ok; ++k) {
                    int f = i + arrf[d]*k, c = j + arrc[d]*k;
                    if (f < 0 or f >= n or c < 0 or c >= m or S[f][c] != s[k]) ok = false;
                }
                if (ok) {
                    busca = false;
                    for (int k = 0; k < s.size(); ++k) {
                        int f = i + arrf[d]*k, c = j + arrc[d]*k;
                        S[f][c] ^= 32;
                    }
                }
            }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (j > 0) cout << " ";
            cout << S[i][j];
        }
        cout << endl;
    }
    cout << endl << (busca?"No":"Si") << endl;
}
 

Para el próximo, ¿queréis algo simple o para pensar un poco?