跳格子游戏
标题:跳格子游戏 | 时间限制: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;
}
