NC50403 嗅探器

题目：

• 某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络，蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息，但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保
证所有的数据包都能被捕获？
输出编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出No solution。

题解：

• 肯定是个割点，但是割点还不够
• 起点到终点不在同一个点双连通分量里
• 起点到终点的路径要经过它，且他是必经之路的第一个点——搜索
在这里插入图片描述
详细讲讲为什么只求割点不行？如果题目给的a，b在一个连通块里，比如图中的2和5，我们求得1为割点，即便将1去掉，2和5依旧相连，所以我们不仅要求出割点，还要验证这个割点能否将a和b隔开
现在我们从a开始tarjan
如果v是u的儿子，当dfn[u]<=low[v]时说明u是割点
删掉u后，u和v必将隔开，如果b在v的一侧，而a不再v的一侧，这样u不就将a和b隔开了吗？
b在v的一侧说明：dfn[b]>=dfn[v]
a在v的另一侧说明：dfn[a]<dfn[v]
如果a在v的一侧，b不在也是同理

代码：

#include<bits/stdc++.h>
#include<vector>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
const int maxn=5e5+9;
vector<int>edge[maxn];
int a,b;
int low[maxn],dfn[maxn];
int cnt=0;
int ans=1e9;
bool check(int x)
{
    if(dfn[x]<=dfn[a]&&dfn[x]>dfn[b])return 1;
    if(dfn[x]<=dfn[b]&&dfn[x]>dfn[a])return 1;
    return 0;
}
void tarjan(int x,int fa)
{
    low[x]=dfn[x]=++cnt;
    for(int i=0;i<edge[x].size();i++)
    {
        int v=edge[x][i];
        if(!dfn[v])
        {
            tarjan(v,x);
            low[x]=min(low[v],low[x]);
            if(low[v]>=dfn[x]&&x!=a&&x!=b&&check(v))
            {
                ans=min(ans,x);
            }
        }
        else if(v!=fa)low[x]=min(low[x],dfn[v]);
    }
}
int main()
{
    int n;
    cin>>n;
    int x,y;
    while(cin>>x>>y)
    {
        if(x==0&&y==0)break;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    cin>>a>>b;
    tarjan(a,a);
    if(ans==1e9)cout<<"No solution";
    else cout<<ans;
}