Given the formulation of your decision problem, first of all notice that you can do binary search to find the max-cut weight $k$, rather than linear search. Secondly, when you test each edge, you get that either the two end points are in the same set, or the two end points are in different sets. Let $S$ be a set on one side of the cut, and let $x_u,x_v$ be boolean indicator variables for whether $u,v$ are in $S$. Then if edge $(u,v)$ crosses the cut, you want $(x_u,x_v) = (1,0)$ or $(0,1)$, and otherwise you want $(x_u,x_v) = (0, 0)$ or $(1,1)$. You can formulate this as a 2-sat problem and solve it in polynomial time to determine membership in set $S$.

Given the formulation of your decision problem, first of all notice that you can do binary search to find the max-cut weight $k$, rather than linear search. Secondly, when you test each edge, you get that either the two end points are in the same set, or the two end points are in different sets. Let $S$ be a set on one side of the cut, and let $x_u,x_v$ be boolean indicator variables for whether $u,v$ are in $S$. Then if edge $(u,v)$ crosses the cut, you want $(x_u,x_v) = (1,0)$ or $(0,1)$, and otherwise you want $(x_u,x_v) = (0, 0)$ or $(1,1)$. You can formulate this as a 2-sat problem and solve it in linear time (linear in the number of edges) to determine membership in set $S$. For example, if $(x_u,x_v) = (0, 0)$ or $(1,1)$ then you would add the two clauses $(x_u \vee \neg x_v) \wedge (\neg x_u \vee x_v)$ to your 2-sat formula.