Skip to Content
CTRL K

Restore Graph

Editorial oficial 

Explicación

Es un poco difícil saber por dónde empezar en este problema, así que probemos un caso mucho más simple: ¿qué pasa si todos los d[i]d[i] son 00 o 11?

En ese caso, d[i]=0d[i]=0 significa que ii es el nodo elegido (del que solo podemos tener uno), y d[i]=1d[i]=1 significa que es un vecino directo (de los que podemos tener a lo sumo kk).

Ahora podemos extender esto para incluir posibilidades donde d[i]=2d[i]=2. Estos nodos tienen que ser vecinos de los nodos con d[i]=1d[i]=1, así que intentamos enlazarlos con los vecinos directos del nodo elegido.

La única forma en que Valera podría haberse equivocado es si la cantidad de nodos que están a distancia d+1d+1 es mayor que k−1k-1Excepto en el caso d=0d=0, en el que es kk. veces la cantidad de nodos que están a distancia dd, porque eso nos forzaría a asignar más aristas de las que permiten las restricciones.

Si se conocen los árboles BFS  (BFS Trees), básicamente estamos construyendo uno de ellos.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

import sys
 
node_num, max_adj = [int(i) for i in input().split()]
 
dists = [[] for _ in range(node_num)]
for n, d in enumerate(input().split()):
	dists[int(d)].append(n)
 
if len(dists[0]) != 1:
	print(-1)  # solo un nodo puede tener distancia 0
	sys.exit()
 
edges = []
for i in range(1, node_num):
	limit = max_adj - (i != 1)
	if len(dists[i]) > len(dists[i - 1]) * limit:
		# la capa actual de nuestro árbol BFS no puede acomodar tantas aristas
		print(-1)
		sys.exit()
 
	# asignamos cada nodo de esta capa a un padre de forma arbitraria
	prev_at = 0
	for n in dists[i]:
		edges.append((dists[i - 1][prev_at // limit], n))
		prev_at += 1
 
print(len(edges))
for a, b in edges:
	print(a + 1, b + 1)
import java.io.*;
import java.util.*;
 
public class RestoreGraph {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int nodeNum = Integer.parseInt(initial.nextToken());
		int maxAdj = Integer.parseInt(initial.nextToken());
 
		StringTokenizer distST = new StringTokenizer(read.readLine());
		List<Integer>[] dists = new ArrayList[nodeNum];
		for (int n = 0; n < nodeNum; n++) { dists[n] = new ArrayList<>(); }
		for (int n = 0; n < nodeNum; n++) {
			dists[Integer.parseInt(distST.nextToken())].add(n);
		}
 
		if (dists[0].size() != 1) {
			System.out.println(-1);  // solo un nodo puede tener distancia 0
			return;
		}
 
		List<int[]> edges = new ArrayList<>();
		for (int i = 1; i < nodeNum; i++) {
			int limit = maxAdj - (i != 1 ? 1 : 0);
			if (dists[i].size() > (long)dists[i - 1].size() * limit) {
				// la capa actual de nuestro árbol BFS no puede acomodar tantas aristas
				System.out.println(-1);
				return;
			}
 
			// asignamos cada nodo de esta capa a un padre de forma arbitraria
			int prevAt = 0;
			for (int n : dists[i]) {
				edges.add(new int[] {dists[i - 1].get(prevAt / limit), n});
				prevAt++;
			}
		}
 
		System.out.println(edges.size());
		for (int[] e : edges) { System.out.println((e[0] + 1) + " " + (e[1] + 1)); }
	}
}
#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int node_num;
	int max_adj;
	std::cin >> node_num >> max_adj;
 
	vector<vector<int>> dists(node_num);
	for (int n = 0; n < node_num; n++) {
		int d;
		std::cin >> d;
		dists[d].push_back(n);
	}
 
	if (dists[0].size() != 1) {
		cout << -1 << endl;
		return 0;
	}
 
	vector<std::pair<int, int>> edges;
	for (int i = 1; i < node_num; i++) {
		int limit = max_adj - (i != 1 ? 1 : 0);
		if (dists[i].size() > (long long)dists[i - 1].size() * limit) {
			// la capa actual de nuestro árbol BFS no puede acomodar tantas aristas
			cout << -1 << endl;
			return 0;
		}
 
		// asignamos cada nodo de esta capa a un padre de forma arbitraria
		int prev_at = 0;
		for (int n : dists[i]) {
			edges.push_back({dists[i - 1][prev_at / limit], n});
			prev_at++;
		}
	}
 
	cout << edges.size() << '\n';
	for (const auto &[a, b] : edges) { cout << a + 1 << ' ' << b + 1 << '\n'; }
}
Fundamentos