Minimum of Maximum Distance to Colored Vertices
Given a tree of N vertices, where a vertex can be colored or uncolored, the task is to determine for each vertex the maximum distance to any of the colored vertices. The task is to find the minimum value among all maximum distances for vertices.
Example:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7marked[] = {2, 6, 7}
Output: 2
Explanation: The maximum distance for each vertex are: [2,3,2,4,4,3,3], minimum is 2
Input:
1
/ \
2 3
/
4marked[] = {4}
Output: 0
Explanation: The maximum distance for each vertex are: [2,1,3,0], minimum is 0.
Approach: To solve the problem, follow the idea below:
The idea lies in the observation that only the marked vertex at the extreme positions will contribute to the answer because the vertex between them will have the minimum distance from marked vertex. Therefore, we just have to return the ceil of distance between two extreme vertex / 2. To find the distance between marked vertices at extreme ends find the distance of all vertices from the first vertex by BFS. Find the farthest marked node from the first node. Then from the farthest marked node found, using BFS find the other farthest marked node.
Step-by-step algorithm:
- If there’s only one marked node, print 0 as the distance to itself will be 0.
- Perform Breadth-First Search (BFS) from the first node.
- Find the farthest marked node from the first node.
- Perform BFS from the farthest marked node found in the previous step.
- Find the farthest marked node from the previously found farthest marked node.
- Print the maximum distance ,i.e the distance between the two farthest node, divided by 2.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
// Function to perform Breadth-First Search (BFS) on a tree
vector<long long> bfs(long long start,
vector<vector<long long> >& tree)
{
queue<long long> q;
q.push(start);
vector<long long> dist(tree.size() + 1, -1);
dist[start] = 0;
// Continue until all nodes are visited
while (!q.empty()) {
long long parent = q.front();
q.pop();
// Visit all children of the current node
for (long long i = 0; i < tree[parent].size();
i++) {
// If the child node hasn't been visited yet
if (dist[tree[parent][i]] == -1) {
// Update the distance and add it to the
// queue
dist[tree[parent][i]] = dist[parent] + 1;
q.push(tree[parent][i]);
}
}
}
return dist;
}
int color(vector<long long> marked,
vector<vector<long long> > tree, int k)
{
// If there's only one marked node, the answer is 0
if (k == 1) {
return 0;
}
vector<long long> dist;
// Perform BFS from the first node
dist = bfs(1, tree);
long long ffmarked = -1, maxi = 0;
// Find the farthest marked node from the first node
for (long long i = 0; i < marked.size(); i++) {
if (dist[marked[i]] > maxi) {
maxi = dist[marked[i]];
ffmarked = marked[i];
}
}
// Perform BFS from the farthest marked node found in
// the previous step
dist = bfs(ffmarked, tree);
maxi = 0;
// Find the farthest marked node from the previously
// found farthest marked node
for (long long i = 0; i < marked.size(); i++) {
if (dist[marked[i]] > maxi) {
maxi = dist[marked[i]];
}
}
// Print the maximum distance divided by 2
return (maxi + 1) / 2;
}
int main()
{
// Test Case 1
long long n = 7, k = 3;
vector<long long> marked = { 2, 6, 7 };
vector<vector<long long> > tree(n + 1,
vector<long long>(0)),
t = { { 1, 2 }, { 1, 3 }, { 2, 4 },
{ 2, 5 }, { 3, 6 }, { 3, 7 } };
for (auto i : t) {
int u = i[0], v = i[1];
tree[u].push_back(v);
tree[v].push_back(u);
}
cout << color(marked, tree, k) << endl;
// Test Case 2
n = 4, k = 1;
vector<long long> marked2 = { 4 };
vector<vector<long long> > tree2(n + 1,
vector<long long>(0)),
t2 = { { 1, 2 }, { 1, 3 }, { 2, 4 } };
for (auto i : t) {
int u = i[0], v = i[1];
tree[u].push_back(v);
tree[v].push_back(u);
}
cout << color(marked2, tree2, k) << endl;
return 0;
}
import java.util.*;
public class Main {
// Function to perform Breadth-First Search (BFS) on a tree
static ArrayList<Long> bfs(long start, ArrayList<ArrayList<Long>> tree) {
Queue<Long> q = new LinkedList<>();
q.add(start);
ArrayList<Long> dist = new ArrayList<>();
for (int i = 0; i <= tree.size(); i++) {
dist.add(-1L);
}
dist.set((int) start, 0L);
// Continue until all nodes are visited
while (!q.isEmpty()) {
long parent = q.poll();
// Visit all children of the current node
for (long child : tree.get((int) parent)) {
// If the child node hasn't been visited yet
if (dist.get((int) child) == -1) {
// Update the distance and add it to the queue
dist.set((int) child, dist.get((int) parent) + 1);
q.add(child);
}
}
}
return dist;
}
static int color(ArrayList<Long> marked, ArrayList<ArrayList<Long>> tree, int k) {
// If there's only one marked node, the answer is 0
if (k == 1) {
return 0;
}
ArrayList<Long> dist;
// Perform BFS from the first node
dist = bfs(1, tree);
long ffmarked = -1, maxi = 0;
// Find the farthest marked node from the first node
for (long m : marked) {
if (dist.get((int) m) > maxi) {
maxi = dist.get((int) m);
ffmarked = m;
}
}
// Perform BFS from the farthest marked node found in the previous step
dist = bfs(ffmarked, tree);
maxi = 0;
// Find the farthest marked node from the previously found farthest marked node
for (long m : marked) {
if (dist.get((int) m) > maxi) {
maxi = dist.get((int) m);
}
}
// Print the maximum distance divided by 2
return (int) ((maxi + 1) / 2);
}
public static void main(String[] args) {
// Test Case 1
long n = 7, k = 3;
ArrayList<Long> marked = new ArrayList<>(Arrays.asList(2L, 6L, 7L));
ArrayList<ArrayList<Long>> tree = new ArrayList<>();
for (int i = 0; i <= n; i++) {
tree.add(new ArrayList<>());
}
int[][] t = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}};
for (int[] edge : t) {
int u = edge[0], v = edge[1];
tree.get(u).add((long) v);
tree.get(v).add((long) u);
}
System.out.println(color(marked, tree, (int) k));
// Test Case 2
n = 4;
k = 1;
ArrayList<Long> marked2 = new ArrayList<>(Collections.singletonList(4L));
ArrayList<ArrayList<Long>> tree2 = new ArrayList<>();
for (int i = 0; i <= n; i++) {
tree2.add(new ArrayList<>());
}
int[][] t2 = {{1, 2}, {1, 3}, {2, 4}};
for (int[] edge : t2) {
int u = edge[0], v = edge[1];
tree2.get(u).add((long) v);
tree2.get(v).add((long) u);
}
System.out.println(color(marked2, tree2, (int) k));
}
}
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
// Function to perform Breadth-First Search (BFS) on a tree
static List<long> bfs(long start, List<List<long>> tree)
{
Queue<long> q = new Queue<long>();
q.Enqueue(start);
List<long> dist = Enumerable.Repeat(-1L, tree.Count + 1).ToList();
dist[(int)start] = 0;
// Continue until all nodes are visited
while (q.Count > 0)
{
long parent = q.Dequeue();
// Visit all children of the current node
for (long i = 0; i < tree[(int)parent].Count; i++)
{
// If the child node hasn't been visited yet
if (dist[(int)tree[(int)parent][(int)i]] == -1)
{
// Update the distance and add it to the queue
dist[(int)tree[(int)parent][(int)i]] = dist[(int)parent] + 1;
q.Enqueue(tree[(int)parent][(int)i]);
}
}
}
return dist;
}
static int color(List<long> marked, List<List<long>> tree, int k)
{
// If there's only one marked node, the answer is 0
if (k == 1)
{
return 0;
}
List<long> dist;
// Perform BFS from the first node
dist = bfs(1, tree);
long ffmarked = -1, maxi = 0;
// Find the farthest marked node from the first node
for (long i = 0; i < marked.Count; i++)
{
if (dist[(int)marked[(int)i]] > maxi)
{
maxi = dist[(int)marked[(int)i]];
ffmarked = marked[(int)i];
}
}
// Perform BFS from the farthest marked node found in the previous step
dist = bfs(ffmarked, tree);
maxi = 0;
// Find the farthest marked node from the previously found farthest marked node
for (long i = 0; i < marked.Count; i++)
{
if (dist[(int)marked[(int)i]] > maxi)
{
maxi = dist[(int)marked[(int)i]];
}
}
// Print the maximum distance divided by 2
return (int)((maxi + 1) / 2);
}
static void Main(string[] args)
{
// Test Case 1
long n = 7, k = 3;
List<long> marked = new List<long> { 2, 6, 7 };
List<List<long>> tree = Enumerable.Range(0, (int)n + 1).Select(x => new List<long>()).ToList();
List<List<long>> t = new List<List<long>> { new List<long> { 1, 2 }, new List<long> { 1, 3 }, new List<long> { 2, 4 },
new List<long> { 2, 5 }, new List<long> { 3, 6 }, new List<long> { 3, 7 } };
foreach (var i in t)
{
int u = (int)i[0], v = (int)i[1];
tree[u].Add(v);
tree[v].Add(u);
}
Console.WriteLine(color(marked, tree, (int)k));
// Test Case 2
n = 4; k = 1;
List<long> marked2 = new List<long> { 4 };
List<List<long>> tree2 = Enumerable.Range(0, (int)n + 1).Select(x => new List<long>()).ToList();
List<List<long>> t2 = new List<List<long>> { new List<long> { 1, 2 }, new List<long> { 1, 3 }, new List<long> { 2, 4 } };
foreach (var i in t2)
{
int u = (int)i[0], v = (int)i[1];
tree2[u].Add(v);
tree2[v].Add(u);
}
Console.WriteLine(color(marked2, tree2, (int)k));
}
}
class Queue {
constructor() {
this.items = [];
}
enqueue(element) {
this.items.push(element);
}
dequeue() {
if (this.isEmpty()) return "Underflow";
return this.items.shift();
}
front() {
if (this.isEmpty()) return "Queue is empty";
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
}
// Function to perform Breadth-First Search (BFS) on a tree
function bfs(start, tree) {
const q = new Queue();
q.enqueue(start);
const dist = Array(tree.length + 1).fill(-1);
dist[start] = 0;
// Continue until all nodes are visited
while (!q.isEmpty()) {
const parent = q.dequeue();
// Visit all children of the current node
for (let i = 0; i < tree[parent].length; i++) {
// If the child node hasn't been visited yet
if (dist[tree[parent][i]] === -1) {
// Update the distance and add it to the queue
dist[tree[parent][i]] = dist[parent] + 1;
q.enqueue(tree[parent][i]);
}
}
}
return dist;
}
function color(marked, tree, k) {
// If there's only one marked node, the answer is 0
if (k === 1) {
return 0;
}
let dist = bfs(1, tree);
let ffmarked = -1,
maxi = 0;
// Find the farthest marked node from the first node
for (let i = 0; i < marked.length; i++) {
if (dist[marked[i]] > maxi) {
maxi = dist[marked[i]];
ffmarked = marked[i];
}
}
// Perform BFS from the farthest marked node found in the previous step
dist = bfs(ffmarked, tree);
maxi = 0;
// Find the farthest marked node from the previously found farthest marked node
for (let i = 0; i < marked.length; i++) {
if (dist[marked[i]] > maxi) {
maxi = dist[marked[i]];
}
}
// Print the maximum distance divided by 2
return Math.floor((maxi + 1) / 2);
}
// Test Case 1
const n = 7,
k = 3;
const marked = [2, 6, 7];
const tree = Array.from({ length: n + 1 }, () => []);
const t = [
[1, 2],
[1, 3],
[2, 4],
[2, 5],
[3, 6],
[3, 7],
];
t.forEach((i) => {
const [u, v] = i;
tree[u].push(v);
tree[v].push(u);
});
console.log(color(marked, tree, k));
// Test Case 2
const n2 = 4,
k2 = 1;
const marked2 = [4];
const tree2 = Array.from({ length: n2 + 1 }, () => []);
const t2 = [
[1, 2],
[1, 3],
[2, 4],
];
t2.forEach((i) => {
const [u, v] = i;
tree2[u].push(v);
tree2[v].push(u);
});
console.log(color(marked2, tree2, k2));
// This code is contributed by akshitaguprzj3
from collections import deque
# Function to perform Breadth-First Search (BFS) on a tree
def bfs(start, tree):
q = deque([start])
dist = [-1 for _ in range(len(tree) + 1)]
dist[start] = 0
# Continue until all nodes are visited
while q:
parent = q.popleft()
# Visit all children of the current node
for i in range(len(tree[parent])):
# If the child node hasn't been visited yet
if dist[tree[parent][i]] == -1:
# Update the distance and add it to the queue
dist[tree[parent][i]] = dist[parent] + 1
q.append(tree[parent][i])
return dist
def color(marked, tree, k):
# If there's only one marked node, the answer is 0
if k == 1:
return 0
# Perform BFS from the first node
dist = bfs(1, tree)
ffmarked = -1
maxi = 0
# Find the farthest marked node from the first node
for i in range(len(marked)):
if dist[marked[i]] > maxi:
maxi = dist[marked[i]]
ffmarked = marked[i]
# Perform BFS from the farthest marked node found in the previous step
dist = bfs(ffmarked, tree)
maxi = 0
# Find the farthest marked node from the previously found farthest marked node
for i in range(len(marked)):
if dist[marked[i]] > maxi:
maxi = dist[marked[i]]
# Print the maximum distance divided by 2
return (maxi + 1) // 2
# Test Case 1
n = 7
k = 3
marked = [2, 6, 7]
tree = [[] for _ in range(n + 1)]
t = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6], [3, 7]]
for i in t:
u, v = i
tree[u].append(v)
tree[v].append(u)
print(color(marked, tree, k))
# Test Case 2
n = 4
k = 1
marked = [4]
tree = [[] for _ in range(n + 1)]
t = [[1, 2], [1, 3], [2, 4]]
for i in t:
u, v = i
tree[u].append(v)
tree[v].append(u)
print(color(marked, tree, k))
Output
2 0
Time Complexity: O(N), where N is the number of nodes in the tree.
Auxiliary Space: O(N)
Contact Us