Ciclovias F2P2 - OBI 2016

ciclovias.cpp

// Ciclovias - F2P2 - OBI 2016
// Rogério Júnior
// Complexidade: O(M*(log M))

#include "bits/stdc++.h"

using namespace std;

#define PB push_back

#define MAXN 100100

vector<int> lista[MAXN];

int n, m, resp[MAXN], maior[MAXN];

int main(){
	
	// leio os valores de n e m
	cin >> n >> m;
	
	// no começo, o maior caminho que começa em cada vértice
	// tem tamanho 1: o próprio vértice
	for(int i=1;i<=n;i++) resp[i]=1;
	
	// leio cada aresta e guardo na lista de adjacencias
	for(int i=0;i<m;i++){

		int a, b;
		cin >> a >> b;

		lista[b].PB(a);
		lista[a].PB(b);
	}
	
	// ordeno os vizinhos de cada vértice
	for(int i=1;i<=n;i++) sort(lista[i].begin(),lista[i].end());
	
	// processo os vértices do maior para o menor
	for(int i=n;i>=1;i--){
		
		// primeiro, calculo o maior caminho de cada sufixo
		maior[lista[i].size()]=0;

		for(int j=lista[i].size()-1;j>=0;j--){

			int v=lista[i][j];

			maior[j]=max(resp[v],maior[j+1]);
		}
		
		// depois o maior caminho de cada vizinho cujo segundo vértice é i
		for(int j=0;j<lista[i].size();j++){

			int v=lista[i][j];
			
			// e atualizo resp[v] para cada vizinho
			resp[v]=max(resp[v],2+maior[j+1]);
		}
	}
	
	// por fim, imprimo a resposta de cada vértice
	for(int i=1;i<=n;i++) cout << resp[i] << " \n"[i==n];
	
	// e retorno zero
	return 0;
}