Assign Values

Problem Overview

• You're given an undirected graph with N vertices and M edges, described by arrays A and B.
• Assign each vertex a unique value from 1..N to maximize the total sum over all edges of their endpoint values.
• Input: N, M, arrays A and B; Output: the maximal achievable edge-sum; isolated vertices do not affect the sum.
• Domain: graph optimization and resource assignment; useful as a coding interview problem and interview question.
• Asked in Microsoft interviews.