Legal or Not

#include<bits/stdc++.h>
using namespace std;

const int Max=100;
vector<int> graph[Max];                                //邻接表实现图。
int indegree[Max]= {0};

bool T(int n) {
    queue<int> node;
    for(int i=0; i<n; i++) {                                             
        if(indegree[i]==0) {
            node.emplace(i);
        }
    }
    int n1=0;
    while(!node.empty()) {
        int u=node.front();
        node.pop();                                                             //删掉度为0的点。
        n1++;
        for(int i=0; i<graph[u].size(); i++) {
            int v=graph[u][i];
            indegree[v]--;                                                        //删掉以度为0为起点的边。
            if(indegree[v]==0) {
                node.emplace(v);
            }
        }
    }
    return n==n1;
}

int main() {
    int n,m;
    while(cin>>n>>m) {
        if(n==0&&m==0) {
            break;
        }
        memset(graph,0,sizeof(graph));
        while(m--) {
            int x,y;
            cin>>x>>y;
            graph[x].emplace_back(y);
            indegree[y]++;
        }
        if(T(n)) {
            cout<<"YES"<<endl;
        } else {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}
全部评论

相关推荐

11-01 20:03
已编辑
门头沟学院 算法工程师
Amazarashi66:这种也是幸存者偏差了,拿不到这个价的才是大多数
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务