git是一种分布式代码管理工具，git通过树的形式记录文件的更改历史，比如： base

friht

#include "stdafx.h"　　#include <iostream>
　　#include <vector>
　　using namespace std;
　　class Solution {
　　public:
　　/**
　　* 返回git树上两点的最近分割点
　　*
　　* @param matrix 接邻矩阵，表示git树，matrix[j] == '1' 当且仅当git树中第i个和第j个节点有连接，节点0为git树的跟节点
　　* @param indexA 节点A的index
　　* @param indexB 节点B的index
　　* @return 整型
　　*/
　　int getSplitNode(vector<string> matrix, int indexA, int indexB) {
　　if (indexA >= matrix.size() || indexB >= matrix.size())
　　{
　　return 0;
　　}
　　vector<int> depth;
　　vector<int> parent;
　　breadTraverl(matrix, depth, parent);
　　int p=0;
　　//如果同一深度，父节点相同，则分割点为父节点
　　//同一深度，父节点不同，寻找父节点的父节点
　　//不同深度，从深度高的往上过滤，每次过滤的时候判断是否达到低的节点的深度；没有之前，要判断低的节点是否是深的节点的父节点
　　if (depth[indexA] == depth[indexB])
　　{
　　int a = indexA;
　　int b = indexB;
　　while (parent[a]!=parent)
　　{
　　a = parent[a];
　　b = parent;
　　}
　　p= parent[a];
　　}
　　else {
　　int a = indexA;//a对应的节点深
　　int b = indexB;
　　bool flag = false;//未找到分割点
　　if (depth[indexA] < depth[indexB])
　　{
　　a = indexB;
　　b = indexA;
　　}
　　while (depth[a]!=depth)//当节点a和节点b不在同一个深度
　　{
　　if (parent[a] == b)
　　{
　　p = b;
　　flag = true;
　　break;
　　}
　　else
　　{
　　--a;
　　}
　　}
　　if (flag == false)
　　{
　　int a = indexA;
　　int b = indexB;
　　while (parent[a] != parent)
　　{
　　a = parent[a];
　　b = parent;
　　}
　　p = parent[a];
　　}
　　}
　　return p;
　　}
　　//广度优先遍历图
　　void breadTraverl(vector<string> matrix, vector<int> &depth, vector<int> &parent)
　　{
　　//visited数组，如何visited为false，则被访问过
　　vector<bool> visited;
　　//  vector<int> depth;
　　//  vector<int> parent;
　　for (int i = 0;i < matrix.size();++i)
　　{
　　visited.push_back(true);
　　depth.push_back(0);
　　parent.push_back(0);
　　}
　　cout << "V_" << 0 << "  ";
　　visited[0] = false;
　　depth[0] = 0;
　　parent[0] = 0;//根节点的本身设置为自己
　　for (int i = 0;i < matrix.size();++i)
　　{
　　//  cout << "matrix[0].length():" << matrix[0].length() << endl;
　　for (int j = 0;j < matrix[0].length();++j)
　　{
　　//注意：此处的matrix[j]应该为'1'而不是1
　　if ((matrix[j] == '1')&& (visited[j] == true))
　　{
　　cout << "matrix[" << i << "]"<<"["<<j<<"]:" << matrix[j] << "  ";
　　cout << "visited["<<j<<"]:" << visited[j] << endl;
　　cout << "V_" << j << "  ";
　　parent[j] = i;
　　depth[j] = depth + 1;
　　visited[j] = false;
　　}
　　}
　　}
　　cout << endl;
　　for (int i = 0;i < matrix.size();i++)
　　{
　　cout << i << ":";
　　cout << "parent:" << parent << "  ";
　　cout << "depth:" << depth << endl;
　　}
　　}
　　};
　　int main()
　　{
　　Solution so;
　　vector<string> matrix;
　　string str1 = "01011";
　　string str2 = "10100";
　　string str3 = "01000";
　　string str4 = "10000";
　　string str5 = "10000";
　　matrix.push_back(str1);
　　matrix.push_back(str2);
　　matrix.push_back(str3);
　　matrix.push_back(str4);
　　matrix.push_back(str5);
　　cout<<"结果："<<so.getSplitNode(matrix, 0, 2);
　　cout << endl;
　　return 0;
　　}