Noic - Avançado - Semana 53 - Problema 2

noic-avancado-s53-p2.cpp

// 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");
}