感谢杭电的水题，A水题，涨自信！
题意描述：
给出M组两个人之间的师徒关系，问是否存在悖论，即某个人的徒弟又是自己的师傅。
解题思路：
用拓扑排序判断图中是否存在环路即可。
拓扑排序参阅：
http://www.cppblog.com/hoolee/archive/2012/08/16/187400.html以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 110
int mp[LEN][LEN];
int d[LEN];
int s[LEN];
int N, M;
int zr;
int findZero()
{
int i;
int a = -1;
for(i = 0; i < N; i++)
if(s[i] == 0 && d[i] == 0)
{
a = i;
break;
}
if(a == -1)
return 0;
zr = a;
return 1;
}
int TopSort()
{
int i, j;
for(i = 0; i < N; i++)
{
if(findZero())
{
s[zr] = 1;
for(j = 0; j < N; j++)
d[j] -= mp[zr][j];
}
else
return 0;//如果点还没有选完，且已经找不到入度为0的点，说明图中存在回路
}
return 1;
}
int main()
{
int i, j;
int x, y;
while(scanf("%d%d", &N, &M), N)
{
memset(mp, 0, sizeof(mp));
memset(s, 0, sizeof(s));
memset(d, 0, sizeof(d));
for(i = 0; i < M; i++)
{
scanf("%d%d", &x, &y);
if(mp[x][y] == 0)
{
mp[x][y] = 1;
d[y]++;
}
}
if(TopSort() == 1)
printf("YES\n");
else
printf("NO\n");
}
//system("pause");
}posted on 2012-08-18 17:39
小鼠标 阅读(600)
评论(0) 编辑 收藏 引用 所属分类:
图论