Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5885 Accepted Submission(s):
2726
题意:输入数据n,m,表示有n个人接下来m行,每行输入x,y表示x是y的师父;
如果A是B的师父B是C的师父,则A是C的师父
如果A是B的师父,B又是A的师父则不合法输出No,如果合法输出YES
题解:1、如果输入的点中无不依赖定点的点(成环)输出no
2、最后结果中不依赖顶点的节点个数少于n不符合题意
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int n,m;
int map[110][110];
int vis[110];
void getmap()
{
int i,j,a,b;
memset(vis,0,sizeof(vis));
memset(map,0,sizeof(map));
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
if(!map[a][b])
{
vis[b]++;
map[a][b]=1;
}
}
}
void tuopu()
{
int i,j,sum=0;
int ok=0;
queue<int>q;
while(!q.empty())
q.pop();
for(i=0;i<n;i++)
{
if(vis[i]==0)
{
sum++;
q.push(i);
}
}
if(sum==0) ok=1;//开始图中就不存在不依赖顶点的节点(成环)
else
{
int u,ans=0;
while(!q.empty())
{
u=q.front();
ans++;
q.pop();
for(i=0;i<n;i++)
{
if(map[u][i])
{
vis[i]--;
if(vis[i]==0)
q.push(i);
}
}
}
if(ans<n)//最后排序完成后不依赖顶点的节点个数小于n
ok=1;//即存在环不符合题意
}
if(ok==0)
printf("YES\n");
else
printf("NO\n");
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m),n|m)
{
getmap();
tuopu();
}
return 0;
}
原文:http://www.cnblogs.com/tonghao/p/4722530.html