题解 | #小米Git#

直接用邻接矩阵解公共节点可能不容易，如果能转化成树的形式会方便很多：

1. 用BFS构造map树结构；
2. 用DFS遍历map，找到两个path表示versionA和versionB的路径，遍历path，第一个不相等的就是最近公共节点

class Solution {
public:
    bool check;
    map<int, vector<int> > BFS(vector<string> &matrix){
        //用BFS，造 父节点->子节点 map
        map<int, vector<int> > mp; //key=node，value=node子节点
        
        deque<int> dq; //先进先出
        dq.push_back(0);
        
        vector<bool> have_find(matrix.size(),false);
        have_find[0]=true;
        
        while (!dq.empty()) {
            int node=dq.front();dq.pop_front();
            for (int i=0; i<matrix.size(); i++) {
                if (matrix[node][i]=='1' && !have_find[i]) {
                    have_find[i]=true;
                    dq.push_back(i);
                    
                    vector<int> tmp;
                    if (mp.find(node)!=mp.end()) {
                        tmp=mp[node];
                    }
                    tmp.push_back(i);
                    mp[node]=tmp;
                }
            }
        }
        
        return mp;
    }
    void DFS(map<int, vector<int> > mp,int node, vector<int> &path, int fnum){
        // 用DFS遍历mp，得到从0节点到fnum的路径path
        if (check) {
            return;
        }
        path.push_back(node);
        if (node==fnum) {
            check=true;
            return;
        }
        vector<int> tmp=mp[node];
        for (auto iter=tmp.begin(); iter!=tmp.end(); iter++) {
            DFS(mp, *iter, path, fnum);
        }
        
        if (!check) {
            path.pop_back();
        }
    }
    int Git(vector<string>& matrix, int versionA, int versionB) {
        if (versionA==versionB||matrix.size()==1) {
            return versionA;
        }
        vector<bool> hasfind(matrix.size(), false);
        map<int, vector<int> > mp=BFS(matrix);
        
        vector<int> path1,path2; //这里用两个path找versionA和versionB，两个path第一个不同的节点就是公共节点
        check=false;
        DFS(mp, 0, path1, versionA);
        check=false;
        DFS(mp, 0, path2, versionB);
        int res;
        for (int i=0; i<path1.size() && i<path2.size(); i++) {
            if (path1[i]==path2[i]) {
                res=path1[i];
            }else
                break;
        }
        return res;
    }
};