Resolução do Problema de Emparelhamento Máximo em Grafos Bipartidos

Dado um grafo bipartido com duas partições: uma à esquerda contendo n1 vértices (numerados de 1 a n1) e outra à direita com n2 vértices (de 1 a n2), e um total de m arestas conectando vértices das duas partes, o objetivo é determinar o número máximo de arestas que podem ser selecionadas de forma que nenhum vértice esteja conectado a mais de uma aresta no subconjunto escolhido.

Um emparelhamento em um grafo bipartido é um conjunto de arestas onde não há vértices compartilhados entre elas. O emparelhamento máximo é o maior desses conjuntos possíveis, e seu tamanho é a resposta desejada.

Formato de Entrada

• A primeira linha contém três inteiros: n1, n2 e m.
• As próximas m linhas contêm dois inteiros por linha: u e v, indicando uma aresta entre o vértice u na parte esquerda e o vértice v na parte direita.

Formato de Saída

Imprima um único inteiro representando o tamanho do emparelhamento máximo.

Restrições

• 1 ≤ n1, n2 ≤ 500
• 1 ≤ u ≤ n1
• 1 ≤ v ≤ n2
• 1 ≤ m ≤ 10⁵

Exemplo de Entrada

2 2 4
1 1
1 2
2 1
2 2

Exemplo de Saída

2

Abodragem Algorítmica

O algoritmo utiliza uma busca em profundidade (DFS) combinada com um sistema de tentativas para atribuir cada vértice da parte esquerda a um vértice da parte direita, respeitando as restrições de exclusividade. A ideia central é tentar associar cada homem (vértice esquerdo) a uma mulher (vértice direito) disponível ou reatribuir mulheres já ocupadas se houver alternativas.

Para isso, mantemos um vetor match, onde match[v] indica qual homem está atualmente emparelhado com a mulher v. Se match[v] == 0, então a mulher v está livre.

Utilizamos uma estrutura de lista de adjacência para representar o grafo de forma eficiente. A função find(u) tenta encontrar um emparelhamento válido para o homem u, exploranndo todas as mulheres adjacentes, marcanod visitações temporárias com um vetor st para evitar ciclos durante a DFS.

Código Implementado

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 600;
const int MAX_M = 100008;

int n_left, n_right, num_edges;
int head[MAX_N];
int edge[MAX_M];
int next_edge[MAX_M];
int match[MAX_N];  // match[j] = i indica que mulher j está ligada ao homem i
bool visited[MAX_N];
int idx = 0;

void add_edge(int u, int v) {
    edge[idx] = v;
    next_edge[idx] = head[u];
    head[u] = idx++;
}

bool dfs(int man) {
    for (int i = head[man]; i != -1; i = next_edge[i]) {
        int woman = edge[i];
        if (visited[woman]) continue;
        visited[woman] = true;

        if (match[woman] == 0 || dfs(match[woman])) {
            match[woman] = man;
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n_left >> n_right >> num_edges;
    memset(head, -1, sizeof(head));
    memset(match, 0, sizeof(match));

    for (int i = 0; i < num_edges; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    int result = 0;
    for (int i = 1; i <= n_left; ++i) {
        memset(visited, false, sizeof(visited));
        if (dfs(i)) {
            result++;
        }
    }

    cout << result << endl;
    return 0;
}