3 ms·
This is a riddle? Just work outward; Each of the destination's adjacent nodes point to it, and recursion does the rest.
by Raphael 19y ago
This is a riddle? Just work outward; Each of the destination's adjacent nodes point to it, and recursion does the rest.
- jcl 19y agoRead the Wikipedia description: http://en.wikipedia.org/wiki/Road_coloring_problem http://en.wikipedia.org/wiki/Road_coloring_problem You can't "point" nodes at each other to communicate the directions to the destination. Instead, you must communicate by coloring each edge with one of k colors (k is the out-degree of every node). Then, for any chosen destination node, you give a sequence of colors; the recipient of the directions starts in any node (even the destination node) and simply follows the sequence of colors, ending up at the destination. The fact that such a coloring always exists is somewhat surprising.