Given a git commit (wiki:...), each commit has an id. Find all the commits
that we have.
给出一个Git的commit，找出所有的parents。每个节点都有一个或多个parent。
另外每个commit都是带着ID的。就是没太懂它是输出所有的commit还是要求逐层打印。
第二题就是找到两个commit的公共祖先。
Git的commit是可以分叉的也可以合并，所以这题其实是个图。
想来真是好久没弄github了。
其实就是BFS和双向BFS，注意好对复杂度的分析吧。优化就是双向BFS吧。
好像不太对。

注意解释下BFS的复杂度为什么是O（V+E）

git commit的题，也是面经题。第一问给一个commit（node），BFS输出所有commits (nodes)。第二问，两个commits （nodes），找到他们的最近的公共parent，就是先BFS一个，然后用map记录下其各个parent到这个commit(node)的距离，然后BFS第二个commit(node)，碰到在map里的node，就算一个总距离，然后更新最短距离和的点，最后最短距离和的点就是结果了，写完面试官也表示很满意。这个注意解释下BFS的复杂度为什么是O（V+E），他会问为什么不是O(V)之类的。

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>

using namespace std;
struct GitNode {
    int id;
    vector<GitNode*> parents;    
    GitNode(int x) : id(x){}
};
vector<int> findParents(GitNode* root) {
    vector<int> res;
    if (!root) return res;    //don't forget!!!!!!!!!!!
    unordered_set<int> visited;
    queue<GitNode*> toVisit;
    toVisit.push(root);
    visited.insert(root->id);    //一定要在这里insert进visited，而不是在pop的时候，因为有可能同一层的点指向同一个点
    while (!toVisit.empty()) {
        GitNode* curr = toVisit.front();
        toVisit.pop();
        res.push_back(curr->id);
        for (auto p : curr->parents)
            if (!visited.count(p->id)){
                visited.insert(p->id);
                toVisit.push(p);
            }
    }
    return res;
}
GitNode* findLCAhelper(queue<GitNode*>& toVisited, unordered_set<GitNode*>& visited, unordered_set<GitNode*>& toCheck) {
    for (int i = toVisited.size(); i > 0; i--) {
        GitNode* curr = toVisited.front();
        toVisited.pop();
        if (toCheck.count(curr)) return curr;
        for (GitNode* p : curr->parents)
            if (!visited.count(p)) {
                visited.insert(p);
                toVisited.push(p);
            }
    }
    return nullptr;
}
GitNode* findLCA(GitNode* n1, GitNode* n2) {
    if (!n1 || !n2) return nullptr;
    queue<GitNode*> toVisited1, toVisited2;
    unordered_set<GitNode*> visited1, visited2;
    toVisited1.push(n1); toVisited2.push(n2);
    visited1.insert(n1); visited2.insert(n2);
    while (!toVisited1.empty() || !toVisited2.empty()) {
        GitNode* tmp = findLCAhelper(toVisited1, visited1, visited2);
        if (tmp) return tmp;
        tmp = findLCAhelper(toVisited2, visited2, visited1);
        if (tmp) return tmp;
    }
    return nullptr;
}
int main(int argc, char *argv[]) {
    /*
    *
    *   5 <-  4  <- 2 <- 6
    *    \      \
    *     \ <- 3 <- 1
    * */
    GitNode* g1 = new GitNode(1);
    GitNode* g2 = new GitNode(2);
    GitNode* g3 = new GitNode(3);
    GitNode* g4 = new GitNode(4);
    GitNode* g5 = new GitNode(5);
    GitNode* g6 = new GitNode(6);

    g1->parents.push_back(g3);
    g1->parents.push_back(g4);
    g2->parents.push_back(g4);
    g3->parents.push_back(g5);
    g4->parents.push_back(g5);
    g6->parents.push_back(g2);

    vector<int> parents = findParents(g1);

    for (int p : parents) cout<<p<<' ';cout<<endl;    //其实这里会漏掉2。。假装是最新git的咯

    cout<<"g1,g6 "<<findLCA(g1, g6)->id<<endl;
    cout<<"g2,g3 "<<findLCA(g2, g3)->id<<endl;
    cout<<"g1,g4 "<<findLCA(g1, g4)->id<<endl;    //觉得这个test是极好的w

}

/*
6 ---------1
|         /
11 5-4-3-2
 \  \
  10-9-8-7

getLCA(1,7)
*/