80pts求思路正确性+求调
查看原帖
80pts求思路正确性+求调
1044970
LucAlva楼主2025/7/25 17:55

思路:求出可联通到终点的点,再分别求出所有出去的路线都可以到达的和有些出去的路线不能达到的,然后BFS找出一条所有点都能到达的路线,代码:

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector <int> a[10010]{};
int st,ed;
int c[10010]{};
bool d[10010]{};
void dfs(int x,int h[]){
    if(x==ed){
        for(int i=1;i<=h[0];i++){
            c[h[i]]=1;
        }
        return;
    }
    for(auto y:a[x]){
        if(!d[y]){
            d[y]=1;
            h[++h[0]]=y;
            dfs(y,h);
            h[0]--;
        }
        else{
            if(c[y]){
                c[x]=1;
            }
        }
    }
    return;
}
void dfs2(int x){
    if(d[x]||c[x]==0||x==ed){
        return;
    }
    d[x]=1;
    for(auto y:a[x]){
        dfs2(y);
        if(!c[y]){
            c[x]=2;
            break;
        }
    }
    return;
}
struct aaa{
    int a,b;
};
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
    }
    scanf("%d%d",&st,&ed);
    for(int i=1;i<=n;i++){
        d[i]=1;
        int h[10010]{};
        h[++h[0]]=i;
        dfs(i,h);
    }
    memset(d,0,sizeof(d));
    dfs2(st);
    if(c[st]==1){
        queue <aaa> f;
        f.push({st,0});
        memset(d,0,sizeof(d));
        d[st]=1;
        int ans=1000000000;
        while(!f.empty()){
            if(f.front().a==ed){
                ans=min(ans,f.front().b);
            }
            else for(auto y:a[f.front().a]){
                if(!d[y]&&c[y]==1){
                    d[y]=1;
                    f.push({y,f.front().b+1});
                }
            }
            f.pop();
        }
        printf("%d",ans);
    }
    else{
        printf("-1");
    }
    return 0;
}
2025/7/25 17:55
加载中...