圖論：最近公共祖先（LCA， Tarjan算法，模闆）

關于Tarjan算法的講解：https://www.cnblogs.com/JVxie/p/4854719.html

重點：

下面詳細介紹一下Tarjan算法的基本思路：

1.任選一個點為根節點，從根節點開始。

2.周遊該點u所有子節點v，并标記這些子節點v已被通路過。

3.若是v還有子節點，傳回2，否則下一步。

4.合并v到u上。

5.尋找與目前點u有詢問關系的點v。

6.若是v已經被通路過了，則可以确認u和v的最近公共祖先為v被合并到的父親節點a。

模闆基于的題目：POJ 1330

#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")

// #include <bits/stdc++.h>
#include <cstdio>
#include <vector>

using namespace std;
typedef pair<int, int>  P;
const int N = 10010;

vector<int> G[N];   // 存樹
vector<P> Q[N];     // 存詢問，first為點，second為此詢問的編号
int used[N];        // 儲存每個節點是否通路過
int deg[N];         // 存每個點的入度
int ans[N];         // 存每次詢問的結果
int pre[N];         // 并查集

void init()    
{
    for(int i=0; i<N; i++)   // 初始化
    {
        used[i] = 0;    // 所有點初始化為未通路過的
        pre[i] = i;     // 并查集初始化
        ans[i] = 0;     // 所有結果初始化為0，因為點是從1開始的
        deg[i] = 0;     // 所有點的入讀都初始化為0
        Q[i].clear();   // 清空詢問
        G[i].clear();   // 清空樹
        
    }
}

int find(int x)     // 并查集，尋找掌門人
{
    if(x == pre[x])
        return x;
    return pre[x] = find(pre[x]);
}
void join(int a, int b) // 并查集，合并兩個點
{
    int fa = find(a);
    int fb = find(b);
    if(fa != fb)
        pre[fa] = fb;
}

void lca(int u)     // 最近公共祖先，u為根節點 
{
    if(G[u].size() == 0)    // 如果目前節點沒有子節點，就标記此點一通路過
        used[u] = 1;
    for(int i=0; i < G[u].size(); i++)  // 如果此點有子節點，先向下遞歸通路子節點
    {
        lca(G[u][i]);
        join(G[u][i], u);   // 将子節點并入到父節點中
        used[u] = 1;        // 子節點通路過後标記此點已通路過
    }   
    for(int i=0; i < Q[u].size(); i++)
    {
        if(used[Q[u][i].first]) // 如果一對詢問點中的另一個也通路過
        {
            ans[Q[u][i].second] = find(Q[u][i].first);
        }
    }
}

void solve(int n)
{
    for(int i=1; i <= n; i++)
    {
        if(deg[i] == 0)     // 根節點是入度為0的點
        {
            lca(i);
        }
    }
}


int main()
{

    int t;
    scanf("%d", &t);
    while(t--)
    {
        init();
        int n, m;
        int a, b;
        scanf("%d", &n);
        m = n -1;
        for(int i=0; i<m; i++)
        {
            scanf("%d %d", &a, &b); // a到b有一條邊
            G[a].push_back(b);
            deg[b] ++;
        }

        int q = 1;  // 1組詢問
        for(int i=1; i <= q; i++)
        {
            scanf("%d %d", &a, &b);
            Q[a].push_back(P(b, i));
            Q[b].push_back(P(a, i));
        }
        solve(n);
        for(int i=1; i <= q; i++)
        {
            if(ans[i] != 0)
                printf("%d\n", ans[i]);
            else 
                printf("Not Connect\n");
        }

    }


    return 0;
}