思路:拓扑排序,如果存在满足所有截图的顺序,那么这个图中就会存在拓扑排序,这意味着图中不会存在循环。因此,我们的目标就是检查图的非循环性。
代码:
int b[200010], vis[200010], edge[200010];
vector<int>a[200010];
void solve(){
int n, k;
cin >> n >> k;
for(int i = 1;i <= n;i ++){
a[i].clear();
edge[i] = 0;
vis[i] = 0;
}
for(int i = 1;i <= k;i ++){
for(int j = 1;j <= n;j ++){
cin >> b[j];
if(j >= 3){
a[b[j - 1]].push_back(b[j]);
edge[b[j]] ++;
}
}
}
if(k == 1){
cout << "Yes\n";
return;
}
queue<int>q;
for(int i = 1;i <= n;i ++)
if(edge[i] == 0)
q.push(i);
while(q.size()){
int x = q.front();
q.pop();
vis[x] = 1;
for(auto y : a[x]){
edge[y] --;
if(edge[y] == 0)
q.push(y);
}
}
for(int i = 1;i <= n;i ++){
if(vis[i] == 0){
cout << "No\n";
return;
}
}
cout << "Yes\n";
}