LibreOJ10101. 「一本通 3.6 练习 2」【ZJOI2004】嗅探器【Tarjan】

嗅探器

【题目描述】

传送门

【题解】

求出S到T经过割点的最小编号,从S开始Tarjan,在Tarjan过程中如果当前子树中存在T点,那么这个割点是有用的,否则抛弃。

代码如下

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=105;
int S,T;
int n,m,cnt,Top,tim,Root,Stk[MAXN],Dfn[MAXN],Low[MAXN],cur[MAXN];
vector<int> G[MAXN];queue<int> que;bool vis[MAXN];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXN*MAXN],son[MAXN*MAXN];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
bool Tarjan(int x){
    int Child=0;Low[x]=Dfn[x]=++tim,Stk[++Top]=x;bool END=0;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(!Dfn[E.son[j]]){
        bool TT=Tarjan(E.son[j]);END|=TT;
        Child++,Low[x]=min(Low[x],Low[E.son[j]]);
        if(TT&&((x==Root&&Child>1)||(x!=Root&&Dfn[x]<=Low[E.son[j]]))) cur[x]=1;
        if(Dfn[x]<=Low[E.son[j]]){
            G[++cnt].clear();
            do{G[cnt].push_back(Stk[Top]);}while(Stk[Top--]!=E.son[j]);
            G[cnt].push_back(x);
        }
    }else Low[x]=min(Low[x],Dfn[E.son[j]]);
    return x==T?1:END;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d",&n);
    for(int x,y;scanf("%d%d",&x,&y),x||y;) E.Add(x,y),E.Add(y,x);
    scanf("%d%d",&S,&T);Tarjan(Root=S);
    for(int i=1;i<=n;i++) if(cur[i]) return printf("%d\n",i),0;
    printf("No solution\n");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部