计算二分图（bipartite graph）交叉点（crossing）的数量

对于一个二分图，如果图的两个部分的顶点都按照顺序分别排列在一对平行线上，如下图，如何计算这个二分图的边有多少个交叉点呢？需要注意两点：1. 在图的顶点处连接的边不认为产生了交叉点，如下图在c、d、B和D点连接的边；2. 如果交叉点有两条以上边经过，这些边中的每对边都要算作产生了一个交叉点，如下图Bd、Cc和Db算作产生了3个交叉点。

那么这个图共有多少个交叉点呢？数一数就可以得出结论，答案是5个。

如果不手工数的话，该怎样计算呢？就以上图为例，首先对图的下半部分顶点按照左右顺序编号为0,1,2,3，然后对上半部分图顶点也进行编号，编号为连接的下半部分顶点的编号，如果连接了多个下半部分的顶点，也要从小到大编上多个编号。则上图上半部分顶点编号为2,0,3,2,1,3。可以看出来，上半部分顶点编号每对逆序（左侧的数大于右侧的数）编号都说明产生了一个交叉点。上图共有5对逆序编号(2,0)，(2,1)，(3,2)，(3,1)，(2,1)，因此共有5个交叉点。现在问题就转化成了如何计算一个数组逆序对的数量，暴力的O(n*n)算法自然很容易想到，但是有没有更高效的方法呢？自然是有的，参考Counting inversion基于归并排序的算法可在O(n*log(n))时间复杂度内实现计算交叉点数量的目的。
原理其实很简单，在归并两个数组有一个比较两个数组元素值的过程，在比较时可以维护一个记录逆序对的变量。如下图：

将A和B归并至C时，发现0小于1，因此将0放入C中，然后发现当前B中的1要小于A中的2，这说明产生了逆序对，逆序对有几个呢？B中的1不止小于A中的2，还小于A中的3，准确的说是A中未被归并的部分和1都组成了一个逆序对。将上述过程进行迭代和递归就可以计算出逆序对的数量，也就是二分图交叉点的数量。
代码如下：

#include <stdio.h>
#include <set>
#include <map>
#include <vector>
#include <algorithm>int mergeAndCount(std::vector<int> &data, int begin, int mid, int end)
{std::vector<int> merged;int result = 0;int i = begin;int j = mid;while (i < mid && j < end){merged.push_back(std::min(data[i], data[j]));if (data[i] > data[j]){result += (mid - i);j++;}else{i++;}}if (i == mid){merged.insert(merged.end(), data.begin() + j, data.begin() + end);}else // j == end{merged.insert(merged.end(), data.begin() + i, data.begin() + mid);}for (int k = 0; k < end - begin; k++){data[k + begin] = merged[k];}return result;
}int sortAndCount(std::vector<int> &data, int begin, int end)
{if ((end - begin) <= 1){return 0;}int mid = (begin + end) / 2;int leftCount = sortAndCount(data, begin, mid);int rightCount = sortAndCount(data, mid, end);int mergeCount = mergeAndCount(data, begin, mid, end);return leftCount + rightCount + mergeCount;
}int twoLayerCrossing(std::vector<std::string> &top, std::vector<std::string> &bottom, std::map<std::string, std::set<std::string> > &adj)
{std::vector<int> toSortAndCount;std::map<std::string, int> bottomName2Order;for (int i = 0; i < bottom.size(); i++){bottomName2Order[bottom[i]] = i;}for (auto &topName : top){std::vector<int> tmp;for (auto &name : adj[topName]){if (bottomName2Order.find(name) != bottomName2Order.end()){tmp.push_back(bottomName2Order.at(name));}}std::sort(tmp.begin(), tmp.end());toSortAndCount.insert(toSortAndCount.end(), tmp.begin(), tmp.end());}printf("Array: ");for (auto num : toSortAndCount){printf("%d ", num);}printf("\n");return sortAndCount(toSortAndCount, 0, toSortAndCount.size());
}int main()
{std::vector<std::string> top = {"A", "B", "C", "D"};std::vector<std::string> bottom = {"a", "b", "c", "d"};std::map<std::string, std::set<std::string>> adj;adj["A"] = {"c"};adj["B"] = {"a", "d"};adj["C"] = {"c"};adj["D"] = {"b", "d"};int result = twoLayerCrossing(top, bottom, adj);printf("result: %d\n", result);
}