杭电-5154Harry and Magical Computer(topo)

快来打我* 2022-08-10 08:37 101阅读 0赞

# Harry and Magical Computer #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)**

Total Submission(s): 1819 Accepted Submission(s): 713

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![Image 1][]  
The next following m lines, each line contains two numbers a b, indicates a dependencies (a, b).  1≤a,b≤n![Image 1][]

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

YES
    NO

topo排序模板

如果每次都能找到一个入度为0的，就能完成，否则不能

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int m,n,map[110][110],degree[110];
    int topo()
    {
    	int i,j,k,mark;
    	for(i=0;i<m;i++)
    	{
    		mark=0;
    		for(j=1;j<=m;j++)
    		{
    			if(degree[j]==0)
    			{
    				mark=1;
    				degree[j]=-1;
    				break;
    			}
    		}
    		if(!mark)
    		return 0;
    		for(k=1;k<=m;k++)
    		{
    			if(map[j][k])
    			degree[k]--;
    		}
    	}
    	return 1;
    }
    int main()
    {
    	int a,b,i,j;
    	while(scanf("%d%d",&m,&n)!=EOF)
    	{
    		memset(map,0,sizeof(map));
    		memset(degree,0,sizeof(degree));
    		for(i=0;i<n;i++)
    		{
    			scanf("%d%d",&a,&b);
    			if(!map[a][b])
    			{
    				map[a][b]=1;
    				degree[b]++;
    			}
    		}
    		int t=topo();
    		if(t)
    		printf("YES\n");
    		else
    		printf("NO\n");
    	}
    	return 0;
    }

[Image 1]: