Harry and Magical Computer

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

3 2
3 1
2 1
3 3
3 2
2 1
1 3

YES
NO

 注意到：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.这一句，就是说b一定要在a前面完成，有一种先后关系，很明显拓扑。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int M = 105;
struct node{
int to, next;
}e[M*M];
bool vis[M];
int in[M], head[M*M];
int n, m, tot;
void init(){
/*for(int i = 0; i < M; ++ i){
/map[i].clear();
in[i] = 0;
vis[i] = 0;
}*/
memset(in, 0, sizeof(in));
memset(head, -1, sizeof(head));
}
void add(int a, int b){
e[tot].to = a;
e[tot].next = head[b];
head[b] = tot++;
}
bool topo(){
memset(vis, 0, sizeof(vis));
int cou = 0, num;
queue<int >q;
for(int i = 1; i <= n; ++i)
if(!in[i]){
vis[i] = 1;q.push(i);
}
while(!q.empty()){
int temp = q.front(); q.pop(); ++cou;
for(int i = head[temp]; ~i; i = e[i].next){
int v = e[i].to;
if(!(--in[v])&&!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
if(cou == n) return 1;
else return 0;
}
int main(){
while(scanf("%d%d", &n, &m) == 2){
init();
int a, b;
tot = 0;
for(int i = 0; i < m; ++ i){
scanf("%d%d", &a, &b);
add(a, b); ++in[a];
}
//cout << "sad"<<endl;
bool flag = topo();
if(flag) cout << "YESn";
else cout << "NOn";
}
return 0;
}

最后

以上就是稳重大雁最近收集整理的关于Hdoj 5154 Harry and Magical Computer 【拓扑】Harry and Magical Computer的全部内容，更多相关Hdoj内容请搜索靠谱客的其他文章。