洛谷5058 [ZJOI2004]嗅探器

题意

在无向图上指定起点和终点，要求找一个节点 $x$ ，使得起点 $st$ 和终点 $ed$ 间所有路径都经过它。

其中点数 $N\le 100$ 。

题解

显然 $x$ 肯定是在起点终点路径上的割点，因为去掉它后起点后终点所在的块就不再连通。

那么从起点出发，找一个割点，保证它与终点连通，即满足 $id[ed]\geq id[y]$ 就行了。还有 $x$ 不能是起点或终点。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
} edge[20005];
int id[105],low[105],dfsord;
int cnt,head[105],n,a,b,st,ed,ans;

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x)
{
    id[x]=low[x]=++dfsord;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!id[y])
        {
            dfs(y);
            low[x]=min(low[x],low[y]);
            if (x!=st && x!=ed && id[x]<=low[y] && id[ed]>=id[y]) ans=min(ans,x);
        }
        else low[x]=min(low[x],id[y]);
    }
}

int main()
{
    n=read();
    for (;;)
    {
        a=read(); b=read();
        if (!a && !b) break;
        add(a,b);
        add(b,a);
    }
    st=read(); ed=read();
    ans=1e9;
    dfs(st);
    return !printf((ans==1e9) ? "No solution" : "%d",ans);
}