Luogu P5058 [ZJOI2004]嗅探器题解（Tarjan求割点+vdcc缩点+Dfs搜索）

Luogu 传送门

这个思路码量有些大，不过跑的挺快的。。

24ms 800kb

看了半天题解发现没有哪位julao用Tarjan求完割点，再将原图缩成一棵树，最后从其中一个信息中心Dfs到另一个信息中心。

大致思路

在Dfs中，传三个值

• id:当前的到了哪个点（缩点后的新编号）
• fa:这个点的父亲（防止Dfs死循环）
• minn:从选定的信息中心到目前为止经过的割点中最小的编号（如果没有经过任何割点就为INF）

具体细节代码有注释

#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<vector>
#include<stack>
using namespace std;
const int MAXN = 110;
const int MAXM = 10010;
const int INF = 0x3f3f3f3f;

template <typename T>
inline void read(T&x){
    x=0; char temp=getchar(); bool f=false;
    while(!isdigit(temp)){if(temp=='-') f=true; temp=getchar();}
    while(isdigit(temp)){x=(x<<1)+(x<<3)+temp-'0'; temp=getchar();}
    if(f) x=-x;
}
template <typename T>
void print(T x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

//basic
int n;
int x,y;
//save edge1
struct node1{
    int to,next;
}edge1[MAXM];
int head1[MAXN],cnt1;
//Tarjan
int dfn[MAXN],low[MAXN],sign;
int root;
bool cut[MAXN]={false};
int vdcc,belong[MAXN];
stack<int> sta;
vector<int> block[MAXN];
//Build
int newid[MAXN];//割点在缩完点图中的新编号
struct node{
    int to,next;
}edge[MAXM];
int head[MAXN],cnt;
int size;
//Dfs
int ans=INF,ori[MAXN<<1];//ori与newid是互逆的，ori用来记录在新图中的编号为i的点原来的编号是多少（只记录割点）

inline void AddEdge1(int u,int v){//加原图的边
    edge1[++cnt1]=(node1){v,head1[u]};
    head1[u]=cnt1;
}

inline void AddEdge(int u,int v){//加新图的边
    edge[++cnt]=(node){v,head[u]};
    head[u]=cnt;
}

void Tarjan(int id,int pre){//割点Tarjan正常操作
    dfn[id]=low[id]=++sign;
    sta.push(id);
    if(id==root&&head1[id]==0){
        block[++vdcc].push_back(id); sta.pop();
        return;
    }
    int sub=0;
    for(register int i=head1[id];i;i=edge1[i].next){
        int aim=edge1[i].to;
        if(dfn[aim]==0){
            sub++;
            Tarjan(aim,i);
            low[id]=min(low[id],low[aim]);
            if((id==root&&sub>1)||(id!=root&&low[aim]>=dfn[id])) cut[id]=true;//判断是否为割点
            if(low[aim]>=dfn[id]){//保存联通块
                vdcc++;
                int temp;
                do{
                    temp=sta.top(); sta.pop();
                    block[vdcc].push_back(temp);
                }while(temp!=aim);
                block[vdcc].push_back(id);
            }
        }
        else if(i!=(pre^1))//可以不用判断
                 low[id]=min(low[id],dfn[aim]);
    }
}

inline void Build(){
    size=vdcc;
    for(register int i=1;i<=n;i++)//给割点单独赋在新图中的编号
        if(cut[i])//判断割点
            newid[i]=++size,ori[newid[i]]=i;
    for(register int i=1;i<=vdcc;i++){
        int temp=block[i].size();
        for(register int j=0;j<temp;j++){
            belong[block[i][j]]=i;//记录原图编号为i的点属于编号为几的联通块
            if(cut[block[i][j]])
                AddEdge(i,newid[block[i][j]]),AddEdge(newid[block[i][j]],i);
        }
    }
}

void Dfs(int id,int fa,int minn){
    if(id==belong[y]){ans=min(ans,minn); return;}
    for(register int i=head[id];i;i=edge[i].next){
        int son=edge[i].to;
        if(son!=fa){
            int temp;
            if(son!=belong[x]&&son!=belong[y]&&son>vdcc) temp=min(minn,ori[son]);//新图中割点的编号是存在newid里的，而newid是由vdcc累加得出的，所以新图编号大于原有的点双联通块的个数的点就是割点，所以minn取这个割点在原图中的编号（记在ori里的）
            else temp=minn;
            Dfs(son,id,temp);
        }
    }
}

int main(){
    read(n);
    while(true){
        int u,v; read(u),read(v); if(u==0&&v==0) break;
        AddEdge1(u,v); AddEdge1(v,u);
    }
    read(x),read(y);

    for(register int i=1;i<=n;i++)
        if(dfn[i]==0)
            root=i,Tarjan(i,0);
    Build();
    Dfs(belong[x],0,INF);
    if(ans==INF) puts("No solution");
    else print(ans);
    return 0;
}