HDU3896 Greatest TC(双联通分量+倍增)

Problem Description

TC (Tian Chao) is magical place, as you all know...
The railways and the rail-stations in TC are fragile and always meet with different kinds of problems. In order to reach the destination safely on time, you are asked to develop a system which has two types of main functions as below.
1: A B C D, reporting whether we can get from station A to station B without passing the railway that connects station C and station D.
2: A B C, reporting whether we can get from station A to station B without passing station C.
Please notice that the railways are UNDIRECTED.

Input

For each test case, the first line will contain two integers N (2<=N<=100000) and M (1<=M<=500000), namely the number of stations and railways in TC. Then each of the next M lines will have two integers, describing the two stations that a certain railway is connecting. After this, there comes a line containing a single integer Q (Q<=300000), which means the number of queries to make on the system. The next Q lines will be queries. Each query begins with a integer, indicating the type of query, followed by 4 (the first type) or 3 (the second type) integers describing the details of the query as what mentioned above.
The stations are always labeled from 1 to N.

Output

For each test case, print "yes" or "no" in separated lines for the queries.

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

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

Source

2011 Multi-University Training Contest 6 - Host by JLU

Recommend

We have carefully selected several similar problems for you: 3894 3891 3892 3895 3899

题解：

无向图，n个点,m条边；

typ==1:

　　a,b,c,d : 判断去掉c和d之间的边之后a,b是否联通；

typ==2:

　　a,b,c:去掉c点之后，a,b是否仍然联通;

思路：先dfs出每个点的dfs序，并处理出每个点的深度以及是否为割点，每条边是否为割边；

对于第一种：（假设c在d的下面）如果a和b一个在c的子树里面，一个不再c的子树里面，并且dc边是桥，则不连通,其他均为联通;

对于第二种：

分成三种情况讨论：

　 1: a,b都在子树c中，如果a,b在c的同一个儿子当中，那么去掉c是联通的；否则让a,b往上跳，变成c的两个儿子，如果lown(a)>=dfn(c) 或 lown(b)>=dfn(c)成立，那么不连通；

　　2：a,b只又一个在子树c中,假设a在子树c中，那么，同样让a往上跳，变成c的儿子,.如果lown[a]>=dfn[c],那么不连通，否则联通;

　　3:a,b都不在子树c中，那么去掉c没有任何影响，所以还是联通(往上跳，可以用倍增法);

参考带码：

#include<bits/stdc++.h>

using namespace std;

#define mod 10007

#define pii pair<int,int>

#define pil pair<int,ll>

#define fi first

#define se second

#define mkp make_pair

#define PI acos(-1.0)

typedef long long ll;

const int INF=0x3f3f3f3f;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return x*f;

}

inline ll readll()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=1e5+;

const int maxm=5e5+;

struct Edge{

    int u,v;

    int nxt;

} edge[maxm<<];

int n,m,head[maxn],tot,times;

int fa[maxn],dep[maxn],dfn[maxn],out[maxn],lown[maxn];

bool iscut[maxn],isbridge[maxn];

int anc[maxn][];

inline void AddEdge(int u,int v)

{

    edge[tot].u=u;

    edge[tot].v=v;

    edge[tot].nxt=head[u];

    head[u]=tot++;

}

inline void Init()

{

    tot=times=;

    memset(head,-,sizeof(head));

    memset(iscut,false,sizeof(iscut));

    memset(isbridge,false,sizeof(isbridge));

    memset(dep,,sizeof(dep));

    memset(fa,,sizeof(fa));

}

inline void dfs(int u)

{

    dfn[u]=lown[u]=++times;

    bool flag=false;

    int child=;

    for(int e=head[u];~e;e=edge[e].nxt)

    {

        int v=edge[e].v;

        if(v==fa[u]) continue;

        if(!dfn[v])

        {

            fa[v]=u;

            dep[v]=dep[u]+;

            dfs(v);

            lown[u]=min(lown[u],lown[v]);

            if(lown[v]>=dfn[u])

            {

                iscut[u]=true;

                if(lown[v]>dfn[u]) isbridge[v]=true;

            }

        }

        else lown[u]=min(lown[u],dfn[v]);

    }

    if(u== && child==) iscut[u]=false;

    out[u]=times;

}

inline bool subtree(int x,int y)

{

    return (dfn[x]>=dfn[y]&&out[x]<=out[y])?:;

}

inline void preprocess()

{

    memset(anc,,sizeof(anc));

    for(int i=;i<=n;++i) anc[i][]=fa[i];

    for(int j=;(<<j)<n;++j)

        for(int i=;i<=n;++i)

            if(anc[i][j-]) anc[i][j]=anc[anc[i][j-]][j-];

}

inline int upward(int u, int x)

{

    for(int i=;i<;i++)

        if((x>>i)&) u=anc[u][i];

    return u;

}

inline bool Judge(int a,int b,int c)

{

    int in1=subtree(a,c);

    int in2=subtree(b,c);

    if(in1&in2)

    {

        a=upward(a,dep[a]-dep[c]-);

        b=upward(b,dep[b]-dep[c]-);

        if(a==b) return true;

        if(lown[a]>=dfn[c]||lown[b]>=dfn[c]) return false;

    }

    if(in1^in2)

    {

        if(!in1) swap(a,b);

        a=upward(a,dep[a]-dep[c]-);

        if(lown[a]>=dfn[c]) return false;

    }

    return true;

}

int main()

{

    scanf("%d%d",&n,&m);

    Init();

    int u,v;

    for(int i=;i<=m;++i)

    {

        u=read(),v=read();

        AddEdge(u,v);AddEdge(v,u);

    }

    dfs();preprocess();

    int q=read();

    while(q--)

    {

        int typ,a,b,c,d;

        typ=read();a=read();b=read();c=read();

        if(typ==)

        {

            d=read();

            if(dep[c]<dep[d]) swap(c,d);

            int temp1=subtree(a,c);

            int temp2=subtree(b,c);

            if(isbridge[c]&&(temp1^temp2)) puts("no");

            else puts("yes");

        }

        else

        {

            bool ok=Judge(a,b,c);

            if(ok) puts("yes");else puts("no");

        }

    }

    return ;

}

巴特西

HDU3896 Greatest TC(双联通分量+倍增)

Problem Description

Input

Output

最新文章

热门文章