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;
}