Fundametnos de Grafos Bipartidos

Um grafo é bipartido se e somente se não contém ciclos de comprimento ímpar. Um método eficiente para verificar essa propriedade é a coloração por busca em profundidade (DFS). A ideia é tentar atribuir dois rótulos (0 ou 1) aos vértices de modo que vértices adjacentes tenham rótulos diferentes. Se em algum momento dois vértices adjacentes receberem o mesmo rótulo, o grafo não é bipartido.

Implementação básica da verificação de bipartição:

function éBipartido(grafo, numVertices):
    cores = array de tamanho numVertices inicializado com -1
    
    function dfs(vértice, corAtual):
        cores[vértice] = corAtual
        for vizinho in grafo[vértice]:
            if cores[vizinho] == corAtual:
                return false
            if cores[vizinho] == -1 and not dfs(vizinho, 1 - corAtual):
                return false
        return true
    
    for v de 0 a numVertices-1:
        if cores[v] == -1:
            if not dfs(v, 0):
                return false
    return true

A complexidade temporal é O(V + E), onde V é o número de vértices e E o número de arestas.

Alternativamente, pode-se utilizar o conceito de conjuntos disjuntos estendidos (ou conjuntos de tipos) para verificar bipartição de forma incremental, o que é particularmente útil em problemas de segmentação temporal, como na questão P5787 - Grafos Bipartidos / Template com Segment Tree. Nessa abordagem, cada vértice é dividido em dois domínios representando os dois lados potenciais do grafo bipartido.

Aplicação: Problema dos Prisioneiros (P1525)

Este problema pede a mínima tensão máxima entre prisioneiros que podem ser separados em duas celas sem conflitos. Uma abordagem eficiente combina busca binária com verificação de bipartição.

Algoritmo:

1. Ordenar as arestas por peso decrescente.
2. Realizar busca binária no limite inferior da tensão.
3. Para cada valor mid da busca binária, construir um grafo apenas com arestas de peso superior a mid e verificar se é bipartido.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Conflito {
    int a, b, intensidade;
};

const int MAXIMO = 100000;
vector<int> adjacencias[MAXIMO];
int rotulos[MAXIMO];

bool colorir(int no, int cor) {
    rotulos[no] = cor;
    for (int viz : adjacencias[no]) {
        if (rotulos[viz] == cor) return false;
        if (rotulos[viz] == -1 && !colorir(viz, 1 - cor)) return false;
    }
    return true;
}

bool viavel(int limite, int vertices, const vector<conflito>& arestas) {
    for (int i = 0; i < vertices; ++i) {
        adjacencias[i].clear();
        rotulos[i] = -1;
    }
    for (const auto& e : arestas) {
        if (e.intensidade > limite) {
            adjacencias[e.a].push_back(e.b);
            adjacencias[e.b].push_back(e.a);
        }
    }
    for (int i = 0; i < vertices; ++i) {
        if (rotulos[i] == -1 && !colorir(i, 0)) return false;
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<conflito> arestas(m);
    for (int i = 0; i < m; ++i) {
        cin >> arestas[i].a >> arestas[i].b >> arestas[i].intensidade;
        arestas[i].a--; arestas[i].b--; // Ajuste para índice baseado em 0
    }
    
    int inferior = 0, superior = 1e9, resposta = 0;
    while (inferior <= superior) {
        int meio = inferior + (superior - inferior) / 2;
        if (viavel(meio, n, arestas)) {
            resposta = meio;
            superior = meio - 1;
        } else {
            inferior = meio + 1;
        }
    }
    cout << resposta << endl;
    return 0;
}
</conflito></conflito></int></algorithm></vector></iostream>

Outra solução utiliza conjuntos disjuntos estendidos com ordenação gulosa das arestas.

Problema do Bloqueio Universitário (P1330)

Para grafos potencialmente desconexos, é necessário verificar cada componente separadamente. A solução ótima consiste em escolher, para cada componente, a menor quantidade entre as duas cores atribuídas pela coloração bipartida.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_NOS = 10000;
vector<int> grafo[MAX_NOS];
int cor[MAX_NOS];
int contagem[2];

bool colorir(int no, int c) {
    cor[no] = c;
    contagem[c]++;
    for (int viz : grafo[no]) {
        if (cor[viz] == c) return false;
        if (cor[viz] == -1 && !colorir(viz, 1 - c)) return false;
    }
    return true;
}

int main() {
    int nos, arestas;
    cin >> nos >> arestas;
    for (int i = 0; i < arestas; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        grafo[u].push_back(v);
        grafo[v].push_back(u);
    }
    
    memset(cor, -1, sizeof(cor));
    int total = 0;
    for (int i = 0; i < nos; ++i) {
        if (cor[i] == -1) {
            contagem[0] = contagem[1] = 0;
            if (!colorir(i, 0)) {
                cout << "Impossível" << endl;
                return 0;
            }
            total += min(contagem[0], contagem[1]);
        }
    }
    cout << total << endl;
    return 0;
}
</int></cstring></vector></iostream>

Problema da Fada (Fairy)

Este problema envolve encontrar arestas cuja remoção torna o grafo bipartido. A abordagem direta de testar cada arestas é ineficiente para grafos maiores. Uma solução linear utiliza a noção de ciclos ímpares e pares, aplicando diferenciação em árvores DFS.

Ao executar uma DFS, os ciclos são identificados por arestas de retorno. Para cada aresta de retorno, determina-se se o ciclo formado é ímpar ou par com base na diferença de profundidades. A diferenciação acumula informações sobre quantos ciclos ímpares/pares passam por cada aresta. A aresta pode ser removida se pertence a todos os ciclos ímpares (ou única) e não está em nenhum ciclo par.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXIMO = 10000;
vector<pair int="">> grafo[MAXIMO]; // (vizinho, id da aresta)
int profundidade[MAXIMO];
int aresta_pai[MAXIMO];
int ciclos_impares[MAXIMO]; // Contagem por aresta
int ciclos_pares[MAXIMO];
int total_impares;
bool eh_arvore[MAXIMO];

void dfs(int no, int pai, int aresta_atual) {
    profundidade[no] = profundidade[pai] + 1;
    aresta_pai[no] = aresta_atual;
    for (auto [viz, id] : grafo[no]) {
        if (viz == pai) continue;
        if (!profundidade[viz]) {
            dfs(viz, no, id);
            eh_arvore[id] = true;
            ciclos_impares[aresta_atual] += ciclos_impares[id];
            ciclos_pares[aresta_atual] += ciclos_pares[id];
        } else if (profundidade[viz] < profundidade[no]) {
            int diferenca = profundidade[no] - profundidade[viz];
            if (diferenca % 2 == 0) {
                ciclos_impares[id]++;
                ciclos_impares[aresta_atual]++;
                ciclos_impares[aresta_pai[viz]]--;
                total_impares++;
            } else {
                ciclos_pares[id]++;
                ciclos_pares[aresta_atual]++;
                ciclos_pares[aresta_pai[viz]]--;
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        grafo[u].emplace_back(v, i);
        grafo[v].emplace_back(u, i);
    }
    
    memset(profundidade, 0, sizeof(profundidade));
    total_impares = 0;
    for (int i = 0; i < n; ++i) {
        if (!profundidade[i]) {
            dfs(i, -1, -1);
        }
    }
    
    vector<int> respostas;
    if (total_impares == 0) {
        for (int i = 0; i < m; ++i) respostas.push_back(i + 1);
    } else {
        for (int i = 0; i < m; ++i) {
            if (eh_arvore[i]) {
                if (ciclos_impares[i] == total_impares && ciclos_pares[i] == 0) {
                    respostas.push_back(i + 1);
                }
            } else {
                if (total_impares == 1 && ciclos_impares[i] == 1) {
                    respostas.push_back(i + 1);
                }
            }
        }
    }
    
    cout << respostas.size() << endl;
    for (int id : respostas) cout << id << " ";
    cout << endl;
    return 0;
}
</int></pair></cstring></vector></iostream>

Problema da Divisão de Membros (P1285)

Este problema envolve particionar vértices em dois grupos balanceados com base em relações de conhecimento. A solução constrói o grafo complementar e aplica coloração bipartida. Cada componente resultante oferece duas possibilidades de tamanho, levando a um problema de mochila 0-1 para minimizar a diferença.

Algoritmo resumido:

1. Calcular o grafo complementar das relações de conhecimento mútuo.
2. Colorir cada componente do complemento; se não for bipartido, não há solução.
3. Para cada componente, registre as contagens de vértices em cada cor (dois tamanhos possíveis).
4. Use programação dinâmica parra selecionar um subconjunto de componentes cuja soma de tamanhos se aproxime de metade do total de vértices.

// Código omitido por brevidade, mas a estrutura segue o descrito.
// A implementação envolve DFS para coloração e DP para balanceamento.