程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1470 LCA tarjan 離線算法

POJ 1470 LCA tarjan 離線算法

編輯：C++入門知識

POJ 1470 LCA tarjan 離線算法

這裡有個講解非常明白，雖然沒證明。點擊打開鏈接還有個數據結構的學習點擊打開鏈接伸展樹/Treap/劃分樹/ 歸並樹

步驟：

tarjan算法的步驟是(當dfs到節點u時):
1 在並查集中建立僅有u的集合,設置該集合的祖先為u
1 對u的每個孩子v:
1.1 tarjan之
1.2 合並v到父節點u的集合,確保集合的祖先是u
2 設置u為已遍歷
3 處理關於u的查詢,若查詢(u,v)中的v已遍歷過,則LCA(u,v)=v所在的集合的祖先

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
/*
 * POJ 1470
 * 給出一顆有向樹，Q個查詢
 * 輸出查詢結果中每個點出現次數
 */
/*
 * LCA離線算法，Tarjan
 * 復雜度O(n+Q);
 */
const int MAXN = 1010;
const int MAXQ = 500010;//查詢數的最大值

//並查集部分
int F[MAXN];//需要初始化為-1
int find(int x)
{
    if(F[x] == -1)return x;
    return F[x] = find(F[x]);
}
void bing(int u,int v)
{
    int t1 = find(u);
    int t2 = find(v);
    if(t1 != t2)
        F[t1] = t2;
}
//************************
bool vis[MAXN];//訪問標記
int ancestor[MAXN];//祖先
struct Edge
{
    int to,next;
}edge[MAXN*2];
int head[MAXN],tot;
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

struct Query
{
    int q,next;
    int index;//查詢編號
}query[MAXQ*2];
int answer[MAXQ];//存儲最後的查詢結果，下標0~Q-1
int h[MAXQ];
int tt;
int Q;

void add_query(int u,int v,int index)
{
    query[tt].q = v;
    query[tt].next = h[u];
    query[tt].index = index;
    h[u] = tt++;
    query[tt].q = u;
    query[tt].next = h[v];
    query[tt].index = index;
    h[v] = tt++;
}

void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
    tt = 0;
    memset(h,-1,sizeof(h));
    memset(vis,false,sizeof(vis));
    memset(F,-1,sizeof(F));
    memset(ancestor,0,sizeof(ancestor));
}

void LCA(int u)
{
    ancestor[u] = u;
    vis[u] = true;
    for(int i = head[u];i != -1;i = edge[i].next)
    {
        int v = edge[i].to;
        if(vis[v])continue;
        LCA(v);
        bing(u,v);
        ancestor[find(u)] = u;
    }
    for(int i = h[u];i != -1;i = query[i].next)
    {
        int v = query[i].q;
        if(vis[v])
        {
            answer[query[i].index] = ancestor[find(v)];
        }
    }
}

bool flag[MAXN];
int Count_num[MAXN];
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    int u,v,k;
    while(scanf("%d",&n) == 1)
    {
        init();
        memset(flag,false,sizeof(flag));
        for(int i = 1;i <= n;i++)
        {
            scanf("%d:(%d)",&u,&k);
            while(k--)
            {
                scanf("%d",&v);
                flag[v] = true;
                addedge(u,v);
                addedge(v,u);
            }
        }
        scanf("%d",&Q);
        for(int i = 0;i < Q;i++)
        {
            char ch;
            cin>>ch;
            scanf("%d %d)",&u,&v);
            add_query(u,v,i);
        }
        int root;
        for(int i = 1;i <= n;i++)
            if(!flag[i])
            {
                root = i;
                break;
            }
        LCA(root);
        memset(Count_num,0,sizeof(Count_num));
        for(int i = 0;i < Q;i++)
            Count_num[answer[i]]++;
        for(int i = 1;i <= n;i++)
            if(Count_num[i] > 0)
                printf("%d:%d\n",i,Count_num[i]);
    }
    return 0;
}