poj 1470 Closest Common Ancestors （離線LCA Tarjan）

題意：求每個點作為lca的次數。

做法：裸的lca題，離線做法就是利用并查集，關鍵思想在于對于目前點的詢問對應的另一個點已經被通路過了，那麼那個點的祖先就是這個詢問的lca。

AC代碼：

//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<ctype.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<string.h>
#include<string>
#include<sstream>
#include<bitset>
using namespace std;
#define ll long long
#define ull unsigned long long
#define eps 1e-8
#define NMAX 1000000000
#define MOD 51123987
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI acos(-1)
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x.end())
template<class T>
inline void scan_d(T &ret)
{
    char c;
    int flag = 0;
    ret=0;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c == '-')
    {
        flag = 1;
        c = getchar();
    }
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
    if(flag) ret = -ret;
}
template<class T> inline T Max(T a, T b){ return a > b ? a : b; }
template<class T> inline T Min(T a, T b){ return a < b ? a : b; }

const int maxn = 1000+10;
struct Edge
{
    int v,next;
}e[maxn*2];
int head[maxn],nct;

inline void add_edge(int u, int v)
{
    e[nct].v = v; e[nct].next = head[u];
    head[u] = nct++;
}

vector<int>v[maxn];
bool vis[maxn],cnt[maxn];
int ans[maxn],fa[maxn];

int findit(int x)
{
    int k = x;
    while(fa[k] != k)
        k = fa[k];
    while(fa[x] != k)
    {
        int tmp = fa[x];
        fa[x] = k;
        x = tmp;
    }
    return k;
}

void dfs(int u)
{
    for(int i = head[u]; i != -1; i = e[i].next)
    {
        int v = e[i].v;
        dfs(v);
        fa[v] = u;
    }
    vis[u] = 1;
    int sz = v[u].size();
    for(int i = 0; i < sz; i++)
        if(vis[v[u][i]])
            ans[findit(v[u][i])]++;
}

int main()
{
#ifdef GLQ
    freopen("input.txt","r",stdin);
//    freopen("o.txt","w",stdout);
#endif
    int n;
    while(~scanf("%d",&n))
    {
        memset(head,-1,sizeof(head));
        nct = 0;
        for(int i = 1; i <= n; i++)
        {
            cnt[i] = vis[i] = false;
            ans[i] = 0;
            fa[i] = i;
            v[i].clear();
        }
        for(int i = 1; i <= n; i++)
        {
            int u,v,t1;
            char c;
            scan_d(u);
            scan_d(t1);
            if(t1 == 0) continue;
            for(int j = 1; j <= t1; j++)
            {
                scan_d(v);
                add_edge(u,v);
                cnt[v] = true;
            }
        }
        int t1;
        scan_d(t1);
        for(int i = 1; i <= t1; i++)
        {
            int x,y;
            char c;
            while((c = getchar()) != '(');
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        while(getchar() != ')');
        for(int i = 1; i <= n; i++)
            if(cnt[i] == false)
            {
                dfs(i);
                break;
            }
        for(int i = 1; i <= n; i++)
            if(ans[i] != 0) printf("%d:%d\n",i,ans[i]);
    }
    return 0;
}