跳格子游戏

标题:跳格子游戏 | 时间限制:1秒 | 内存限制:262144K 
地上共有N个格子,你需要跳完地上所有的格子,但是格子间是有强依赖关系的,跳完前一个格子后,后续的格子才会被开启,格子间的依赖关系由多组steps数组给出,steps[0]表示前一个格子,steps[1]表示steps[0]可以开启的格子:
比如[0,1]表示从跳完第0个格子以后第1个格子就开启了,比如[2,1],[2,3]表示跳完第2个格子后第1个格子和第3个格子就被开启了
请你计算是否能由给出的steps数组跳完所有的格子,如果可以输出yes,否则输出no

说明:
1.你可以从一个格子跳到任意一个开启的格子
2.没有前置依赖条件的格子默认就是开启的
3.如果总数是N,则所有的格子编号为[0,1,2,3....N-1]连续的数组

#include <iostream>
#include <set>
#include <queue>
using namespace std;

typedef struct {
    int in;
    set<int> next;
}Node;

int main()
{
    int n=0;
    cin >> n;
    Node *s=new Node[n];
    int a,b;
    while(cin>>a>>b) {
        s[a].next.insert(b);
        s[b].in++;
    }
    
    queue<int> q;
    
    set<int> visit;
    
    for(int i=0;i<n;i++) {
        if(s[i].in==0) {
            q.push(i);
            visit.insert(i);
        }
    }
    
    if(q.size()==0) {
        cout << "no";
        return 0;
    }
    
    while(!q.empty()) {
        int front=q.front();
        q.pop();
        
        for(set<int>::iterator it=s[front].next.begin();it!=s[front].next.end();it++) 
            if(visit.find(*it)==visit.end()) {
                q.push(*it);
                visit.insert(*it);
            }
    }
    
    if(visit.size()!=n) cout<<"no";
    else cout<<"yes";
    
    delete[] s;
    return 0;
}




全部评论

相关推荐

点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务