JZOJ1418. 【COCI 2007】盗賊を追う

タイトルの説明
Descriptionは警察が逃げている犯罪者を捕まえるのを助けるために、新しいコンピュータシステムを発明しました.警察が統制する区域はN都市で、都市間にはE本の双方向辺が接続され、都市番号は1からNである.警察は、犯罪者がある都市から別の都市に逃亡する過程で彼を捕まえようとすることが多い.捜査員は地図をよく研究して、どの都市に障害を設けたり、道を断ち切ったりするかを決めています.あなたのコンピュータシステムは以下の2つの質問に答えなければなりません:1、都市G 1とG 2を結ぶ道が閉鎖されたら、犯罪者は都市Aから都市Bに逃げることができますか?2、もし都市Cが閉鎖されたら、犯罪者は都市Aから都市Bに逃げることができますか?プログラミングは上記のコンピュータシステムを実現する.
Input入力の最初の行には、2つの整数NおよびE(2<=N<=10000,1<=E<=500000)が含まれ、都市およびエッジの数を表す.次のE行は、各行に2つの異なる整数AiとBiが含まれており、都市AiとBiの間に1つのエッジが直接接続されていることを示し、任意の2つの都市の間には最大1つのエッジしか接続されていないことを示しています.次の行は、質問回数を表す整数Q(1<=Q<=300000)を含む.次にQ行は、1行あたり4個または5個の整数を含み、1番目の数は1または2であり、質問の種類を表す.問題の種類が1であれば、後に4つの整数A,B,G 1,G 2について、G 1とG 2の間の道路が閉鎖された場合、犯罪者が都市Aから都市Bに逃げることができるかどうかを尋ね、AとBが異なることを保証し、G 1とG 2の間に必ず道路があることを示す.質問の種類が2であれば、後に3つの整数A、B、C、3つの数が互いに異なり、都市Cを閉鎖すれば、犯罪者が都市Aから都市Bに逃げることができるかどうかを尋ねる.入力データは、最初は任意の2つの都市が互いに到着することを保証します.Outputは質問ごとに「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
問題解
実は分けてやるのは難しくないのですが...
問い合わせ1
まずTarjan縮環(図強連通成分がなく、1つのエッジを通るたびに逆のエッジを歩かない)を行い、その後、削除したエッジが強い連通成分の中にあれば、影響はありません.さもないとdfsシーケンスで判断します
問い合わせ2
Tarjanのdfsツリーでやります.
cがa~bの点に影響を及ぼすことができれば、cは必ずa~bの経路上、あるいはcはa or bの祖先であり、abのlcaはcの祖先である.この点からcへの経路で最もcに近い点(cの息子の一人である)をxとし、1つの点がcを削除しても連通していれば、xのサブツリーには必ず1つの点がcの祖先に戻ることができる.
そしてlow[x]とdfn[c]を判断すればよい.
code

#include 
#include 
#include 
#include 
#include 
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a
using namespace std;

int a[1000002][3];
struct BB{int x,y,z;} b[1000002];
int ls[100001];
int Ls[100001];
int dfn[100001];
int low[100001];
int Dfn[100001][2];
int Df[100001][2];
int num[100001];
int fa[100001][17];
bool bz[100001];
bool Bz[500001];
int d[100001];
int D[100001];
int dp[100001];
int N,n,m,i,j,k,l,len,L,Q,s1,s2,s3,s4,s5,S;

void swap(int &x,int &y)
{
    int z=x;
    x=y;
    y=z;
}

bool cmp(BB a,BB b) {return a.xvoid New(int x,int y)
{
    len++;
    a[len][0]=y;
    a[len][1]=ls[x];
    a[len][2]=x;
    ls[x]=len;
}

void Read()
{
    len=1;
    scanf("%d%d",&n,&m);
    fo(i,1,m)
    {
        scanf("%d%d",&j,&k);
        New(j,k);New(k,j);
    }
}

void tj(int t)
{
    int i;

    Df[t][0]=++S;
    fo(i,1,16)
    fa[t][i]=fa[fa[t][i-1]][i-1];

    dfn[t]=++j;
    low[t]=j;
    d[++L]=t;
    bz[t]=1;

    for (i=ls[t]; i; i=a[i][1])
    if (!Bz[i>>1])
    {
        Bz[i>>1]=1;

        if (!dfn[a[i][0]])
        {
            fa[a[i][0]][0]=t;
            dp[a[i][0]]=dp[t]+1;
            tj(a[i][0]);
        }
        if (bz[a[i][0]]) low[t]=min(low[t],low[a[i][0]]);

        Bz[i>>1]=0;
    }

    Df[t][1]=S;

    if (dfn[t]==low[t])
    {
        k++;
        for (; d[L+1]!=t; num[d[L--]]=k) bz[d[L]]=0;
    }
}

void dfs(int t,int Fa)
{
    Dfn[t][0]=++j;

    for (int i=Ls[t]; i; i=b[i].z)
    if (b[i].y!=Fa)
    dfs(b[i].y,t);

    Dfn[t][1]=j;
}

bool Inc(int x,int y) {return Dfn[x][0]<=Dfn[y][0] && Dfn[y][1]<=Dfn[x][1];}
bool inc(int x,int y) {return Df[x][0]<=Df[y][0] && Df[y][1]<=Df[x][1];}

int lca(int i,int j)
{
    int k;

    if (dp[i]for (k=16; dp[i]>dp[j]; i=(dp[fa[i][k]]>=dp[j])?fa[i][k]:i,k--);

    fd(k,16,0) if (fa[i][k]!=fa[j][k]) i=fa[i][k],j=fa[j][k];
    if (i!=j) i=fa[i][0];

    return i;
}

bool pd(int s1,int s2)
{
    int i,k;

    if (inc(s2,s1))
    {
        for (k=16,i=s1; k>=0; i=(dp[fa[i][k]]>dp[s2])?fa[i][k]:i,k--);
        if (low[i]>=dfn[s2])
        {
            printf("no
");
            return 1;
        }
        return 0;
    } else return 0;
}

void Sort()
{
    fo(i,2,len)
    b[i].x=num[a[i][2]],b[i].y=num[a[i][0]];
    stable_sort(b+2,b+len+1,cmp);
    j=0;
    k=len;
    fo(i,2,len)
    if (b[i].x!=b[i].y && (b[i].x!=b[i-1].x || b[i].y!=b[i-1].y))
    {
        j++;
        b[j].x=b[i].x;
        b[j].y=b[i].y;
        b[j].z=Ls[b[j].x];
        Ls[b[j].x]=j;
    }
    len=j;
}

void work1()
{
    scanf("%d",&s5);
    s2=num[s2];s3=num[s3];s4=num[s4];s5=num[s5];

    if (!Inc(s4,s5)) swap(s4,s5);
    if ((Inc(s5,s2) && !Inc(s5,s3) || !Inc(s5,s2) && Inc(s5,s3)) && s4!=s5)
    printf("no
"); else printf("yes
");
}

void work2()
{
    l=lca(s2,s3);

    if (inc(s4,l) && s4!=l || !inc(s4,s2) && !inc(s4,s3)) printf("yes
");
    else
    {
        if (pd(s2,s4)) return;
        if (pd(s3,s4)) return;

        printf("yes
");
    }
}

void Tarjan()
{
    j=0;L=0;k=0;
    tj(1);
    N=k;
}

int main()
{
    Read();
    Tarjan();
    Sort();

    j=0;dfs(1,0);

    for (scanf("%d",&Q); Q; Q--)
    {
        scanf("%d%d%d%d",&s1,&s2,&s3,&s4);
        if (s1==1) work1(); else work2();
    }

    return 0;
}