感謝杭電的水題，A水題，漲自信！
題意描述：
給出M組兩個人之間的師徒關系，問是否存在悖論，即某個人的徒弟又是自己的師傅。
解題思路：
用拓撲排序判斷圖中是否存在環路即可。
拓撲排序參閱：
http://www.shnenglu.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
小鼠標 閱讀(611)
評論(0) 編輯 收藏 引用 所屬分類:
圖論