java - 算法题 航线交叉

Question

航线交叉
有一条河道，河道南北两侧分别有n个城市，0 < n < 100，南北的城市之间有航线相连，但是有的航线是有交叉的，容易产生事故。现在已知每个城市有且只有一条航线与对岸的某个城市相连，希望减少一些航线来避免事故，请问减少的最小航线数是多少？
例如上图中，需要去掉的航线数是3，分别是1-2, 4-4, 6-3这三条（其中前面一个数字表示北面的城市号，后一个数字表示南面的城市号）。
输入的第一个数是城市数n，接下来2个数为一组，有n组城市航线对，第一个数字代表北面的城市号，后一个数字代表南面的城市号。
输出为需要减少的最少航线数。
样例输入：
6 1 2 2 1 3 5 4 4 5 6 6 3
样例输出：
3

Answer 1

Traverse nodes 1-n to calculate the number of intersections in each city, remove the most, and repeat multiple times until there are no intersections.
Method for calculating intersection:
a b c d
boolean = (a-c)*(c-d)<0.

Answer 2

Use the places and cities where the routes intersect as nodes, add a source node and destination, and use the maximum flow.
Assignment of edges, assuming that the source node is on the top and the end point is on the bottom. Before the first crossing, each edge is assigned a value of 1. After the first crossing, the one with the least number of crossings is selected to be assigned a value of 1, and the rest are assigned a value of 0. It has not been proven that the algorithm is correct, but after some brainstorming, it should be correct, and I am too lazy to prove it.

Answer 3

Set the starting point and end point as two column vectors, then subtract the starting point value from the end point value, and find the route that is not less than 0 and remove it.

Answer 4

Sort in ascending order of city numbers on one side, find the longest non-decreasing sequence of city numbers on the other side, and subtract the found sequence length from the total number of cities.