1.git是一种分布式代码管理工具，git通过树的形式记录文件的更改历史，比方： base'<--base<--A<--A' ^ | --- B<--B' 小米project师经常须要寻找两个分支近期的切割点，即base.如果git 树是多叉树，请实现一个算法。计算git树上随意两点的近期切割点。
（如果git树节点数为n,用邻接矩阵的形式表示git树：字符串数组matrix包括n个字符串，每一个字符串由字符'0'或'1'组成。长度为n。matrix[i][j]=='1'当且仅当git树种第i个和第j个节点有连接。节点0为git树的根节点。）
#include<vector>
#include<string>
#include<iostream>
using namespace std;
int getSplitNode(vector<string> matrix, int indexA, int indexB) {
int m = matrix.size();
vector<vector<int>> fu(m);
for (int i = 0; i < m; i++)
for (int j = i+1; j < m; j++)
{
if (matrix[i][j] == '1')
fu[i].push_back(j);
}
vector<int> a;
vector<int> b;
int t1 = 0;
a.push_back(indexA);
int t2 = 0;
b.push_back(indexB);
while (indexA != 0){
for (int i = 0; i < fu.size(); i++)
{
for (int j = 0; j < fu[i].size(); j++){
if (fu[i][j] == indexA)
{
a.push_back(i);
indexA = i;
break;
}
}
if (indexA == 0)
break;
}
}
while (indexB > 0){
for (int i = 0; i < fu.size(); i++){
for (int j = 0; j < fu[i].size(); j++){
if (fu[i][j] == indexB)
{
b.push_back(i);
indexB = i;
break;
}
}
if (indexB == 0)
break;
}
}
t1 = a.size();
t2 = b.size();
t1--;
t2--;
while (a[t1] == b[t2]){
t1--;
t2--;
if (t1 < 0 || t2 < 0)
break;
}
return a[++t1];
}
int main()
{
vector<string> matrix = { "011001", "100010", "100100", "001000", "010000","100000" };
/*matrix[0] = "01011";
matrix[1] = "10100";
matrix[2] = "01000";
matrix[3] = "10000";
matrix[4] = "10000";*/
cout << getSplitNode(matrix, 5, 3) << endl;
getchar();
}