题面
1523 嗅探器
一句话题意：求路径上割点的数量。（又够短了吧）
思路
用Tarjin做加点处理即可。就看Tarjin这一部分。
首先一个点k如果符合条件，则它一定是一个割点。
其次，遍历它的所有边k->m，则q是k子树上的一点（不然到不了），因而总能找到一个点m使q也为m的子树上一点（或者q==m），那么dfn[q]>=dfn[m]（这一点好好想一想）
最后，k!=p（k也不等于q，但是不用考虑了，因为子树这一点达不到）
因此就有这个if语句
if(k!=p&&dfn[a[i].to]<=dfn[q]&&low[a[i].to]>=dfn[k])
ans=min(ans,k);//先是割点，然后不是pq，而且q为k子树
然后是全部的Tarjin函数，就是在求割点的代码上略加改进。
stack<int> st;
void tarjin(int k)
{
dfn[k]=low[k]=++tot;
int cntt=0;
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to])
{
cntt++,tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
if(k!=p&&dfn[a[i].to]<=dfn[q]&&low[a[i].to]>=dfn[k])
ans=min(ans,k);//先是割点，然后不是pq，而且q为k子树
}
else low[k]=min(low[k],dfn[a[i].to]);
}
代码
直接上代码，不多说。
#include <bits/stdc++.h>
using namespace std;
int n,x,y,p,q,ans=1e9;
int head[200005],cnt;
int dfn[200005],low[200005],tot,rt;
struct node
{
int to,nxt;
} a[1000005];
void add(int x,int y)
{
a[++cnt].to=y,a[cnt].nxt=head[x],head[x]=cnt;
}
stack<int> st;
void tarjin(int k)
{
dfn[k]=low[k]=++tot;
int cntt=0;
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to])
{
cntt++,tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
if(k!=p&&dfn[a[i].to]<=dfn[q]&&low[a[i].to]>=dfn[k])
ans=min(ans,k);//先是割点，然后不是pq，而且q为k子树
}
else low[k]=min(low[k],dfn[a[i].to]);
}
int main()
{
scanf("%d%d%d",&n,&x,&y);
while(x!=0&&y!=0) add(x,y),add(y,x),scanf("%d%d",&x,&y);
scanf("%d%d",&p,&q);
rt=p,tarjin(p);
if(ans>1e8) printf("No solution\n");
else printf("%d\n",ans);
return 0;
}
小结
这道题目又是比较简单的题目，求答案的时候需要灵活应用，不要硬缩点、硬dfs……还是比较巧妙、有思考水平的一道题目。
有什么问题，欢迎私信。
完结撒花！！！
别忘了点赞，关注，谢谢！！
