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;
}