題面：

Harry and Magical Computer Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2183????Accepted Submission(s): 862


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

YES NO

題意：

???? 任務(wù)之間有依賴關(guān)系，如a->b，那么必須先完成任務(wù)b，才能完成任務(wù)a，問是否能夠完成全部任務(wù)。

解題：

??? 經(jīng)典的拓?fù)渑判?，找入度?的點(diǎn)，不斷入隊(duì)列，廣搜即可，最后看是否所有點(diǎn)都被訪問了。

代碼：

#include#include#include#include#define?inf?1000000
using?namespace?std;
struct?edge
{
????int?fm,to,nxt;
}store[10010];
int?in[105],vis[105],head[105],n,cnt;
void?addedge(int?a,int?b)
{
????store[cnt].nxt=head[a];
????head[a]=cnt;
????store[cnt].fm=a;
????store[cnt++].to=b;
}
queueq;
void?bfs()
{
???int?cur;
???for(int?i=1;i<=n;i++)
???????if(in[i]==0)
???????????q.push(i);
???while(!q.empty())
???{
???????cur=q.front();
???????q.pop();
???????vis[cur]=1;
???????for(int?i=head[cur];~i;i=store[i].nxt)
???????{
???????????int?v=store[i].to;
???????????in[v]--;
???????????if(in[v]==0)
???????????????q.push(v);
???????}
???}
}
int?main()
{
????int?m,a,b;
????while(~scanf("%d%d",&n,&m))
????{
????????cnt=0;
????????memset(head,-1,sizeof(head));
????????memset(in,0,sizeof(in));
????????memset(vis,0,sizeof(vis));
????????for(int?i=0;i<m;i++)
????????{
????????????scanf("%d%d",&a,&b);
????????????addedge(b,a);
????????????in[a]++;
????????}
????????bfs();
????????bool?flag=1;
????????for(int?i=1;i<=n;i++)
????????{
????????????if(vis[i]==0)
????????????{
????????????????flag=0;
????????????????break;
????????????}
????????}
????????if(flag)
????????????printf("YESn");
????????else
????????????printf("NOn");
????}
????return?0;
}