Solução por Lúcio Cardoso
Usaremos o seguinte Lema:
Lema: Um grafo é bipartido se e somente se não possui nenhum ciclo de tamanho ímpar.
Com esse lema, é possível observar que ou o grafo será bipartido em todas as inserções de arestas, ou haverá uma aresta 
de índice mínimo tal que após ser inserida, o grafo nunca será bipartido (e em todas as inserções anteriores ele será bipartido). Isso acontece porque assim que um ciclo ímpar for formado no grafo, ele nunca poderá ser desfeito.
Com isso, podemos fazer uma busca binária para achar o índice da aresta , caso ela exista. Dessa forma, imprimimos "Sim" para as arestas de índice menor que o de e "Não" para as arestas seguintes.
Na busca binária, para checar se uma aresta 
é a menor aresta desejada, vamos inserir todas as arestas de índice menor ou igual a e checar se o grafo resultante é bipartido ou não.
Para checar se o grafo é bipartido, executaremos o seguinte algoritmo:
1. Para cada componente conexa do grafo, inicie uma BFS em um vértice qualquer desta componente e pinte esse vértice com a cor 
.
2. Durante a BFS, pinte cada vizinho 
de um vértice 
com a cor 
caso a cor de seja , ou com a cor caso contrário.
3. Após a BFS ser realizada, o grafo será bipartido se e somente se não existirem dois vértices ligados por uma aresta que possuam a mesma cor.
Para mais informações sobre o lema e o algoritmo apresentados, clique aqui.
A complexidade final é, então, 
. Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Noic - Avançado - Semana 53 - Problema 2 | |
| // O((N+M)*log M) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 1e5+10; | |
| typedef pair<int, int> pii; | |
| int n, m; | |
| pii edge[maxn]; // arestas dadas na entrada | |
| bool cor[maxn]; // cor de cada vértice ao executar a bfs | |
| bool mark[maxn]; // vértices marcados na bfs | |
| vector<int> grafo[maxn]; | |
| void bfs(int u) | |
| { | |
| queue<int> fila; | |
| fila.push(u), mark[u] = 1, cor[u] = 0; | |
| while (!fila.empty()) | |
| { | |
| int u = fila.front(); | |
| fila.pop(); | |
| for (auto v: grafo[u]) | |
| if (!mark[v]) | |
| fila.push(v), mark[v] = 1, cor[v] = !cor[u]; | |
| } | |
| } | |
| bool bipartite(int j) | |
| { | |
| // limpamos o grafo e o vetor de vértices marcados | |
| memset(mark, 0, sizeof mark); | |
| for (int i = 1; i <= n; i++) | |
| grafo[i].clear(); | |
| for (int i = 1; i <= j; i++) | |
| { | |
| int u = edge[i].first, v = edge[i].second; | |
| grafo[u].push_back(v); grafo[v].push_back(u); | |
| } | |
| for (int i = 1; i <= n; i++) | |
| if (!mark[i]) // nova componente conexa | |
| bfs(i); | |
| for (int u = 1; u <= n; u++) | |
| for (auto v: grafo[u]) | |
| if (cor[u] == cor[v]) | |
| return false; | |
| return true; | |
| } | |
| // encontra a primeira aresta que torna o grafo não-bipartido | |
| int busca(void) | |
| { | |
| int ini = 1, fim = m, ans = m+1; | |
| while (ini <= fim) | |
| { | |
| int mid = (ini+fim)>>1; | |
| if (!bipartite(mid)) fim = mid-1, ans = mid; | |
| else ini = mid+1; | |
| } | |
| return ans; | |
| } | |
| int main(void) | |
| { | |
| scanf("%d %d", &n, &m); | |
| for (int i = 1; i <= m; i++) | |
| scanf("%d %d", &edge[i].first, &edge[i].second); | |
| int e = busca(); // primeira aresta que torna o grafo não-bipartido | |
| for (int i = 1; i < e; i++) | |
| printf("Sim\n"); | |
| for (int i = e; i <= m; i++) | |
| printf("Não\n"); | |
| } |