Harry and Magical Computer
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1845 Accepted Submission(s): 727
Problem Description
In reward of being yearly outstanding magic student, Harry gets a magical computer. When the computer begins to deal with a process, it will work until the ending of the processes. One day the computer got n processes to deal with. We number the processes from 1 to n. However there are some dependencies between some processes. When there exists a dependencies (a, b), it means process b must be finished before process a. By knowing all the m dependencies, Harry wants to know if the computer can finish all the n processes.
Input
There are several test cases, you should process to the end of file.
For each test case, there are two numbers n m on the first line, indicates the number processes and the number of dependencies.
1≤n≤100,1≤m≤10000
The next following m lines, each line contains two numbers a b, indicates a dependencies (a, b).
1≤a,b≤n
Output
Output one line for each test case.
If the computer can finish all the process print "YES" (Without quotes).
Else print "NO" (Without quotes).
Sample Input
3 2
3 1
2 1
3 3
3 2
2 1
1 3
Sample Output
题意：一共有n个任务，共有m条条件，对于m条条件来说：要完成a，需要先完成b。问最后能否完成所有任务。
a依赖于b，要完成a，需要完成任务b。典型的拓扑排序条件：全序条件。这里直接上代码：
#include<stdio.h>
#include<string.h>
using namespace std;
int a[110][110];
int degree[110];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(a,0,sizeof(a));
memset(degree,0,sizeof(degree));
for(int i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(a[x][y]==0)
{
a[x][y]=1;
degree[y]++;//入度
}
}
int jieshu=0;
int cont=0;
while(1)
{
int j=1;
if(degree[j]!=0)
{
while(1)
{
j++;
if(degree[j]==0)break;
if(j>n)break;
}
}
if(j>n)//如果说当前没有了度为0的点，break就行。
break;
degree[j]=-1;
cont++;
if(cont==n)
{
jieshu=1;
break;
}
for(int i=1;i<=n;i++)
{
if(a[j][i]>0)
{
degree[i]--;
a[j][i]=-1;
}
}
}
if(jieshu==1)
printf("YES\n");
else
printf("NO\n");
}
}