题解 P5058 【[ZJOI2004]嗅探器】

gcwixsxr · 2020-06-01 20:53:58 · 题解

这是一道割点的板子题

其实这道题挺水的

在板子上加一道特判就可以了..

为了简化问题，我们直接从 a 点开始做DFS。

对于一个割点 u ，若判定 u 为割点的边是 (u,v),那么有以下讨论,

• 如果 dfn[b] < dfn[u]，则 b 是 u 的祖先或者 b 和 u 不在同一个子树内，由于 a 是根，那么 a和 b 一定在一个连通块内。

• 如果 dfn[b] > dfn[u] \,\ and \,\ dfn[b] <dfn[v]，则 b 是 v 的兄弟子树中的节点，无法确定 a,b 是否在一个连通块。

• 如果 dfn[b] >= dfn[v]，则 b 是 v 的子树中的节点，a,b 一定不在一个连通块。

大概这三种情况就对应上述三种图

综上满足dfn[b] >= dfn[v]就行

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int to,next;
}e[1000010];
int n,m,stindex,ei,ans;
int a,b;
int h[200010],dfn[200010],low[200010];
bool u[200010];
void add (int x,int y)
{   
    ei++;
    e[ei].to=y;
    e[ei].next=h[x];
    h[x]=ei;
}
void tarjan(int f, int fa)
{
    int cnt = 0;
    stindex++;
    low[f]=dfn[f]=stindex;
    for(int i=h[f];i;i=e[i].next)
    {
        if(e[i].to==fa)continue;
        cnt++;
        int to = e[i].to;
        if(dfn[to]==0)
        {
            tarjan(to,f);
            if((fa==0&&cnt>1||fa!=0&&low[to]>=dfn[f])&&dfn[b]>=dfn[to])//相对板子tarjan部分就只改了这一句
            {
                u[f]=1;
            }
            low[f] = min(low[f],low[to]);
        }else
        {
            low[f] = min(low[f],dfn[to]);
        }
    }
}
int main(){
    scanf ("%d",&n);
    int xx,yy;
    while(scanf("%d%d",&xx,&yy)&&xx&&yy){
        add (xx,yy);
        add (yy,xx);
    }
    scanf("%d%d",&a,&b);
    tarjan (a,0);
    for (int i=1;i<=n;i++)
        if (u[i])return printf ("%d\n",i),0;
    printf("No solution\n");
    return 0;
}