欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu3342 Legal or Not【拓扑排序】

程序员文章站 2024-03-19 12:00:10
...

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3342
题意:有n个人,他们之间有着师徒关系,现在告诉你m组关系(x,y),即x是y的师傅,现在问你这些关系是否出现混乱
解析:题目求解拓扑排序是否有可行解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
vector<int>G[maxn];
int in[maxn];
bool topu(int n)
{
    queue<int>q;
    for(int i=0;i<n;i++)
    {
        if(!in[i])
            q.push(i);
    }
    int cnt = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        cnt++;
        for(int i = 0;i<(int)G[u].size();i++)
        {
            int v = G[u][i];
            if(--in[v]==0)
                q.push(v);
        }
    }
    return cnt==n;
}
int main(void)
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        if(!n && !m)
            break;
        memset(in,0,sizeof(in));
        for(int i=0;i<n;i++)
            G[i].clear();
        for(int i=0;i<m;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            G[x].push_back(y);
            in[y]++;
        }
        if(topu(n))
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}