双连通分量 之 一本通1523 嗅探器

题面

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……还是比较巧妙、有思考水平的一道题目。
有什么问题，欢迎私信。

完结撒花！！！
别忘了点赞，关注，谢谢！！