U115596 互动小说

hulaquan · 2024-01-22 21:18:04 · 个人记录

构建图：

• 点：页码
• 边：页码之间的可达关系

对图进行BFS：

• BFS中的层次即起点到该点的最短路径
• 整本书的终点为出度为0的点
• 如果有节点没有被广搜到，即是多余的

每个节点拓展一次，时间复杂度O(N)

M1 + M2 + … + Mn <=10000，即总边数<=10000，空间复杂度O(点数N+总边数)

#include<bits/stdc++.h>
using namespace std;
int n,m,t,ans=-1;
vector<int> g[10005];  
int minstep[10005]; //每页的最短路径 
queue<int> que;
void bfs(){
    que.push(1);minstep[1]=1;
    while(!que.empty()){
        int u=que.front();que.pop();
        if(ans==-1 && g[u].size()==0){ //首次到达结局，即为最少页数 
            ans=minstep[u]; 
        } 
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i];
            if(!minstep[v]){
                que.push(v),minstep[v]=minstep[u]+1;
            }
        }  
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        for(int j=1;j<=m;j++){
            cin>>t;
            g[i].push_back(t);
        }
    }
    bfs();
    bool flag=1;  //假设每页都可达到 
    for(int i=1;i<=n;i++)
        if(!minstep[i]){ // minstep[i]为0，说明第i页不能到达
            flag=0;break;
        } 
    if(flag) cout<<"Y"<<endl<<ans; 
    else cout<<"N"<<endl<<ans; 
}