生活随笔
收集整理的這篇文章主要介紹了
hdu 4547(LCA+Tarjan)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
解題思路：很明顯的LCA問題，用Tarjan離線算法即可。這里輸入的可能是字符串，所以直接用map保存。此外，根據(jù)題意，這里需要稍稍有點變化，因為cd：a\b\c...這里是一步即可完成，所以在查詢a和b時，還要判斷與公共祖先的關(guān)系。還要注意，這道題沒有告訴根節(jié)點，所以可以根據(jù)入度為0來判斷根節(jié)點。
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;const int maxn = 100005;
const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;
struct Edge
{int to,next;
}edge[maxn];
struct Ask
{int to,next,id,lca;
}ask[maxn<<1];
struct Query
{int a,b;
}q[maxn];
int n,m,cnt,cnt1,cnt2,pre[maxn],head[maxn];
int fa[maxn],color[maxn],dis[maxn],in[maxn],lca[maxn];
bool vis[maxn];
map<string,int> mp;void init()
{mp.clear();memset(pre,-1,sizeof(pre));memset(head,-1,sizeof(head));memset(in,0,sizeof(in));memset(color,0,sizeof(color));cnt = cnt1 = cnt2 = 0;
}void addedge(int u,int v)
{edge[cnt1].to = v;edge[cnt1].next = pre[u];pre[u] = cnt1++;
}void addask(int u,int v,int id)
{ask[cnt2].to = v;ask[cnt2].id = id;ask[cnt2].next = head[u];head[u] = cnt2++;
}int find(int x)
{if(fa[x] == x) return x;return fa[x] = find(fa[x]);
}void Tarjan(int u,int dep)
{fa[u] = u;dis[u] = dep;color[u] = GRAY;for(int i = pre[u]; i != -1; i = edge[i].next){int v = edge[i].to;Tarjan(v,dep+1);fa[v] = u;}color[u] = BLACK;for(int i = head[u]; i != -1; i = ask[i].next){int v = ask[i].to;if(color[u] == BLACK){int ancestor = find(v);lca[ask[i].id] = ancestor;}}
}int main()
{int t;string A,B;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);init();for(int i = 1; i < n; i++){cin >> A >> B;if(mp.find(A) == mp.end())mp[A] = cnt++;if(mp.find(B) == mp.end())mp[B] = cnt++;addedge(mp[B],mp[A]);in[mp[A]]++;}for(int i = 1; i <= m; i++){cin >> A >> B;addask(mp[A],mp[B],i);addask(mp[B],mp[A],i);q[i].a = mp[A], q[i].b = mp[B];}int root;for(int i = 0; i < n; i++)if(in[i] == 0){root = i;break;}Tarjan(root,0);for(int i = 1; i <= m; i++){int ancestor = lca[i];int a = q[i].a;int b = q[i].b;if(a == b)printf("0\n");else if(a == ancestor)printf("1\n");else if(b == ancestor)printf("%d\n",dis[a] - dis[b]);else printf("%d\n",dis[a] - dis[ancestor] + 1);}}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的hdu 4547(LCA+Tarjan)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
