---

追捕盗贼(COCI2007)

Description

为了帮助警察抓住在逃的罪犯，你发明了一个新的计算机系统。警察控制的区域有N个城市，城市之间有E条双向边连接，城市编号为1到N。

警察经常想在罪犯从一个城市逃亡另一个城市的过程中抓住他。侦查员在仔细研究地图，以决定在哪个城市设置障碍，或者断掉某条路。你的计算机系统必须回答以下两种问题：

1、 如果连接城市G1和G2的路被封掉，罪犯能否从城市A逃到城市B？

2、 如果城市C被封掉，罪犯能否从城市A逃到城市B？

编程实现上述计算机系统。

Input Format

输入第一行包含两个整数N和E(2<=N<=100000,1<=E<=500000)，表示城市和边的数量。

接下来E行，每行包含两个不同的整数Ai和Bi，表示城市Ai和Bi之间有一条边直接相连，任意两个城市之间最多只有一条边相连。

接下来一行包含一个整数Q(1<=Q<=300000)，表示询问次数。

接下来Q行，每行包含4个或5个整数，第一个数为1或2，表示询问问题的种类。

如果问题种类是1，后面跟着4个整数A,B,G1,G2，如上描述表示询问如果G1和G2之间的路封掉罪犯能否从城市A逃到城市B，保证A和B不同，G1和G2之间一定存在路。

如果问题种类是2，后面跟着三个整数A,B,C，三个数互不相同，表示询问如果封掉城市C，罪犯能否从城市A逃到城市B。

输入数据保证一开始任意两个城市都可以相互到达。

Output Format

每个询问输出一行“yes”或“no”。

Sample Input

13 15 1 2 2 3 3 5 2 4 4 6 2 6 1 4 1 7 7 8 7 9 7 10 8 11 8 12 9 12 12 13 5 1 5 13 1 2 1 6 2 1 4 1 13 6 7 8 2 13 6 7 2 13 6 8

Sample Output

yes  yes  yes  no  yes

解析

这是一道\(Tarjan\)算法的综合运用题，考察了了有关割点割边等内容。

由于询问的数量较多，我们考虑离线的\(Tarjan\)算法，将原图化为一棵搜索树。

先看一下第一问，和割边的格式有些相似。我们先考虑封掉的边是不是割边。如果不是割边，则对连通性没有影响。如果是割边，我们可以利用如下方法判定。

设封掉的边连接的两个点为\(G1\)，\(G2\)。(深度较深的为\(G1\))

1.点\(A\)在以\(G1\)为根的子树中，但点\(B\)不在以\(G1\)为根的子树中。

2.点\(B\)在以\(G1\)为根的子树中，但点\(A\)不在以\(G1\)为根的子树中。

由于一条割边只能将原图分为两个不同的联通块，所以当两个条件满足一个时，割边必然将\(A\)，\(B\)两点分在了不同的联通块中。

割边我们可以在做\(Tarjan\)时求出，考虑如何判断某个点\(P1\)是否在以点\(P2\)为根的子树中。

我们重新记录一个值\(Maxdfn_x\)代表以x为根的子树中的最大\(dfn\)值。由于一个节点的\(dfn\)值必然比他的祖先节点的\(dfn\)值小，我们就可以利用\(Maxdfn\)数组得到\(subtree\)函数。

inline bool subtree(int p1,int p2)//代表p1是否在以p2为根的子树中{    return dfn[p1]>=dfn[p2]&&dfn[p1]<=Maxdfn[p2];}

一遍\(Tarjan\)就可以解决第一问，考虑如何解决第二问。

我们仍然要求\(C\)点为割点，由于一个割点会将图分为若干个连通分量，我们需要做特殊的记录。对于每一个\(2\)号询问，设\(yA\)代表点\(C\)到点\(A\)路径上的第一个点的编号，\(yB\)代表点\(C\)到点\(B\)路径上的第一个点的编号。

如果\(A\)，\(B\)不在同一条路径上，即\(yA≠yB\)，并且\(yA\)没有能够向上跳超过\(C\)点的返祖边，或者\(yB\)没有能够向上跳超过\(C\)点的返祖边\(B\)，那么\(A\)，\(B\)必然不能互达。

只要求出\(yA\)，\(yB\)就可以了，可以用如下方法：

设\(askA_x\)代表对于某个\(2\)号询问中\(A\)点为\(x\)的询问编号，\(askB_x\)代表对于某个\(2\)号询问中\(B\)点为\(x\)的询问编号，\(askCa_x\)代表某个\(2\)号询问中\(A\)点要求封掉的点\(C\)编号为\(x\)的询问编号，\(askCb_x\)代表某个\(2\)号询问中\(B\)点要求封掉的点\(C\)编号为\(x\)的询问编号。

对于\(Tarjan\)访问到每一个点x时，我们将\(askA_x,askB_x\)一一取出，并以\(C\)节点作为下标将询问编号统计加入\(askCa,askCb\)数组中，在回溯到父节点时，我们就可以方便地统计得到每一个询问的\(yA\)，\(yB\)值。

这样问题就得到了解决。

\(Code:\)

#include
    
     using namespace std;const int N=100000+200,E=500000+200,Q=300000+200;int n,m,q,Last[E*2],t,dfn[N],low[N],Maxdfn[N],cnt=0,yA[Q],yB[Q];struct edge{int ver,next;}e[E*2];struct question{int a,b,c,x,y,index;}ques[Q];vector < int > askA[N],askB[N],askCa[N],askCb[N];inline void insert(int x,int y){    e[++t].ver=y;e[t].next=Last[x];Last[x]=t;}inline void input(void){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++)    {        int u,v;        scanf("%d%d",&u,&v);        insert(u,v);        insert(v,u);    }    scanf("%d",&q);    for(int i=1;i<=q;i++)    {        int index;        scanf("%d",&ques[i].index);        if(ques[i].index==1)            scanf("%d%d%d%d",&ques[i].a,&ques[i].b,&ques[i].x,&ques[i].y);        if(ques[i].index==2)        {            scanf("%d%d%d",&ques[i].a,&ques[i].b,&ques[i].c);            askA[ques[i].a].push_back(i);            askB[ques[i].b].push_back(i);        }    }} inline void Tarjan(int x,int fa){    dfn[x]=low[x]=++cnt;    while(askA[x].size())    {        int num=askA[x].back();        if(dfn[ques[num].c])            askCa[ques[num].c].push_back(num);        askA[x].pop_back();    }    while(askB[x].size())    {        int num=askB[x].back();        if(dfn[ques[num].c])            askCb[ques[num].c].push_back(num);        askB[x].pop_back();    }    for(int i=Last[x];i;i=e[i].next)    {        int y=e[i].ver;        if(y==fa)continue;        if(!dfn[y])        {            Tarjan(y,x);            low[x]=min(low[x],low[y]);            while(askCa[x].size())            {                yA[askCa[x].back()]=y;                askCa[x].pop_back();            }            while(askCb[x].size())            {                yB[askCb[x].back()]=y;                askCb[x].pop_back();            }        }        else low[x]=min(low[x],dfn[y]);    }    Maxdfn[x]=cnt;}inline bool subtree(int p1,int p2){    return dfn[p1]>=dfn[p2]&&dfn[p1]<=Maxdfn[p2];}inline void answer(void){    for(int i=1;i<=q;i++)    {        if(ques[i].index==1)        {            if(ques[i].x==ques[i].y)printf("yes\n");            else            {                if(dfn[ques[i].x]
     
      =dfn[ques[i].c]) || (yB[i]&&low[yB[i]]>=dfn[ques[i].c]) )                printf("no\n");            else printf("yes\n");        }    } }int main(void){    freopen("data.in","r",stdin);    freopen("data.out","w",stdout);    input();    for(int i=1;i<=n;i++)        if(!dfn[i])Tarjan(i,0);    answer();    return 0;}
     
    

---