Hyacinth

Introduction

This problem asks you take a tree and assign up to two values per node, such that all adjacent nodes share a common value, and the number of unique values assigned is maximized.

Solutions

Greedy/BFS

Idea

So long as each internal node uses both of its values with some adjacent node, it doesn't matter which edges are used by which values. This is only true because it's a tree. If there were loops, it would get much more complicated.

Two cases:

1. No internal nodes: just assign the same to values to the nodes
2. Internal nodes: pick a "start" internal node. Assign it two values (0 and 1 sound good). Alternating between the two values, choose an adjacent node, and fix it's first value to the chosen value from our start node. This guarantees that both values are used by some edge. Run BFS, and when you reach a node, choose the next unused value as the nodes second value (remember we assigned it's first value from the preceding node), and the assign the first values of all it's successor nodes to one of the two values (ensuring both are used somewhere). When you reach an edge node, assign any frequency.

Runtime

• n

Code

Solution - Java

import java.util.*;
public class h {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new h().go();
	}
	private void go() {
		int n=in.nextInt();
		int ord=0;
		HashMap<Integer, HashSet<Integer>>hm=new HashMap<Integer,HashSet<Integer>>();
		for(int i=1;i<n;i++){
			int ii=in.nextInt();
			int j=in.nextInt();
			if(!hm.containsKey(ii))hm.put(ii, new HashSet<Integer>());
			if(!hm.containsKey(j))hm.put(j, new HashSet<Integer>());
			hm.get(ii).add(j);
			hm.get(j).add(ii);
		}
		TreeSet<Integer> visited=new TreeSet<Integer>();
		int[][] ass=new int[n+1][2];
		for(int i=0;i<ass.length;i++)for(int j=0;j<ass[0].length;j++)ass[i][j]=-1;
		Queue<Integer> q=new LinkedList<Integer>();
		for(int i:hm.keySet())if(hm.get(i).size()!=1){//Start with a non-leaf node
			q.add(i);
			ass[i][0]=ord++;//assumption is this comes from previous node
			break;
		}
		if(q.isEmpty()){//degenerate case
			System.out.println("0 1");
			System.out.println("1 0");
			System.exit(0);
		}
		while(!q.isEmpty()){
			int on=q.poll();
			int s=1;
			ass[on][1]=ord++;
			visited.add(on);
			for(int i:hm.get(on)){
				if(!visited.contains(i)){
					ass[i][0]=ass[on][s++%2];//for most nodes we can just use the new frequency...but for first node, gotta ensure both get used..so just alternate
					q.offer(i);
				}
			}
		}
		for(int i=1;i<n+1;i++)System.out.printf("%d %d\n",ass[i][0],ass[i][1]);
	}
}