本文共 1326 字，大约阅读时间需要 4 分钟。
2586.
这个题以前写过在线LCA(ST)的，
现在贴一个离线Tarjan版的
代码:
1 //A-HDU2586-LCA-tarjan离线版 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 using namespace std; 21 typedef long long ll; 22 23 const double PI=acos(-1.0); 24 const double eps=1e-6; 25 const ll mod=1e9+7; 26 const int inf=0x3f3f3f3f; 27 const int maxn=4e4+10; 28 const int maxm=100+10; 29 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 30 31 struct node{ 32 int x,y; 33 //node(int xx,int yy){ 34 // x=xx,y=yy; 35 //}node(){} 36 }; 37 38 vector edge[maxn],q[maxn]; 39 int ans[maxn],dis[maxn],fa[maxn],vis[maxn]; 40 int n,m,aa,bb,cc; 41 42 int find(int x)//找父节点(祖先) 43 { 44 return x==fa[x]?x:fa[x]=find(fa[x]); 45 } 46 47 void unio(int x,int y)//并查集压缩路径 48 { 49 fa[find(y)]=find(x); 50 } 51 52 void init()//初始化 53 { 54 for(int i=1;i<=n;i++){ 55 edge[i].clear(); 56 q[i].clear(); 57 fa[i]=i;//初始化自己的父亲节点是自己 58 vis[i]=0; 59 ans[i]=0; 60 dis[i]=0; 61 } 62 } 63 64 void dfs(int x)//tarjan 65 { 66 vis[x]=1; 67 for(int i=0;i
溜了。
转载于:https://www.cnblogs.com/ZERO-/p/9525826.html