站外题求助
  • 板块题目总版
  • 楼主Firstly
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/3/18 10:44
  • 上次更新2023/10/28 06:20:43
查看原帖
站外题求助
525898
Firstly楼主2022/3/18 10:44

原题链接

写了个拓扑排序判环,结果 WA 了最后一个点,求各位大佬指点

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int N=1005;
vector<vector<int> >g;
int ind[N],n;
inline bool topsort(){
    for(int i=0;i<n;i++)
        for(int j=0;j<g[i].size();j++)
            ind[g[i][j]]++;
    queue<int>q;
    for(int i=0;i<n;i++)
        if(!ind[i])q.push(i);
    int sum=0;
    while(!q.empty()){
        int vt=q.front();
        q.pop();sum++;
        for(int i=0;i<g[vt].size();i++){
            ind[g[vt][i]]--;
            if(!ind[g[vt][i]])
                q.push(g[vt][i]);
        }
    }return !(sum==n);
}
int main(){
    cin>>n;g.resize(n+2);
    for(int i=0;i<n;i++){
        int m;cin>>m;
        for(int i=0;i<m;i++){
            int v;cin>>v;
            g[i].push_back(v);
        }
    }cout<<(topsort()?"No":"Yes");
    return 0;
}
2022/3/18 10:44
加载中...