求解一个最大二分匹配的问题，要求时间是O(V^2)

Question

已知一条河两岸都有若干个城市，两岸的若干个城市之间都有若干条固定的航线。
而两岸的每个城市之间都有一个“唯一友好城市”，并且这些“唯一友好城市”对之间的两个城市必须有航线相连。
请设计一个算法在O(V^2)的时间内找出最大数量的“唯一友好城市”对，并且保证这些城市对之间的航线不会使船相撞（即航线不相交）。

PS：我期末考的时候这题没做出来，而且最后还挂了，明年还要重修。。。
因为题目限定了时间复杂度，所以一直想不出解决方法，求各位大神能不能给出个具体思路，谢谢了~

Answer 1

参考