搜索应用小结

YFF1 · 2024-11-20 14:05:57 · 个人记录

判环

几大判环方法：

DFS(有向图):

void check(int u){
    use[u]=1;
    for(int i:g[u]){
        if(use[i]==1){
            f=1;
            return ;
        }
        if(use[i]==0)check(i);
    }
    use[u]=2;
}

拓扑排序：

bool check(){
    for(int i=0;i<n;i++){
        rd[i]=0;
        g[i].clear();
    }
    for(int i=1;i<=m;i++){
        g[u[i]].push_back(v[i]);
        rd[v[i]]++;
    }
    queue<int>q;
    int cnt=0;
    for(int i=0;i<n;i++){
        if(rd[i]==0)q.push(i),cnt++;
    }
    while(!q.empty()){
        int pos=q.front();
        q.pop();
        for(int i:g[pos]){
            if(--rd[i]==0)q.push(i),cnt++;
        }
    }
    if(cnt!=n)return 0;
    else return 1;
}

SPFA(判负环):

bool spfa() {
    for(int i=1;i<=n;i++){
        q.push(i);
        vis[i]=true;
    }
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        vis[x]=0; 
        for(pii i:g[x]) { 
            if(dis[i.first]>dis[x]+i.second){
                dis[i.first]=dis[x]+i.second;
                cnt[i.first]=cnt[x]+1;
                if(cnt[i.first]>=n)return true;
                if(!vis[i.first]){ 
                    vis[i.first]=1; 
                    q.push(i.first);
                }
            }
        }
    }
    return false;
}

实际上，在正式的应用中，除了负权环之外，比较常用的是DFS和SPFA。一般而言，DFS可以快速知道具体每个点在不在环上，但是拓扑排序可以知道整个图有没有环，而且可以知道整个图中没有在环上的点的总数。

比如可以用拓扑排序的题https://www.luogu.com.cn/problem/AT_abc296_e

可以用DFS判环的题https://www.luogu.com.cn/problem/CF936B