CodeForces 178B1 - Greedy Merchants tarjan求双联通分量+tarjan离线求最近公共祖先

网友投稿 302 2022-08-25

CodeForces 178B1 - Greedy Merchants tarjan求双联通分量+tarjan离线求最近公共祖先

题意:

有一个联通无向图...有K个商人要在K对点间运货...问这K个商人各自经过了多少个桥...

题解:

此题用到了两个tarjan..第一个tarjan是用来求双联通分量缩点的..第二个tarjan是用来离线求一堆点对的最近公用祖先...

既然是要找桥...那么首先对这个无向图进行缩点...把每个双联通块缩成一个点...这样图就成了一颗树..树中的每条边都是桥...问题转化为在一颗树中从一点到另一点的距离...数据范围这么大..想到了LCA...完全不记得怎么用tarjan求LCA了..看了各种资料..才写出来...

关于tarjan求LCA...这个博文不错摘抄最经典的一段:

//parent为并查集，FIND为并查集的查找操作//QUERY为询问结点对集合//TREE为基图有根树 Tarjan(u) visit[u] = true for each (u, v) in QUERY if visit[v] ans(u, v) = FIND(v) for each (u, v) in TREE if !visit[v] Tarjan(v) parent[v] = u

Program:

#include#include#include#include#include#include#include#include#include#define ll long long#define eps 1e-5#define oo 1000000007#define pi acos(-1.0)#define MAXN 500005using namespace std;struct node{ int x,y,id,next;}line[MAXN];struct NODE{ int y,w;};int Lnum,top[MAXN],_next[MAXN],dfn[MAXN],low[MAXN],DfsIndex,ans[MAXN],father[MAXN];int tp[MAXN],tpnum;bool used[MAXN],bridge[MAXN];void addline(int x,int y,int id){ line[++Lnum].next=_next[x],_next[x]=Lnum; line[Lnum].x=x,line[Lnum].y=y,line[Lnum].id=id;}vector T[MAXN];void tarjan(int x,int id){ int y,k; dfn[x]=low[x]=++DfsIndex; for (k=_next[x];k;k=line[k].next) if (line[k].id!=id) { y=line[k].y; if (!dfn[y]) { tarjan(y,line[k].id); low[x]=min(low[x],low[y]); if (dfn[x]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数据
上一篇:汽车行业再现“擦边”营销现象：丝袜换挡、下单就能亲？
下一篇:hiho一下 第二十一周 离散化与线段树回顾
相关文章

 发表评论

暂时没有评论，来抢沙发吧~