3.1模拟题 problem2 万妖穴

题目描述
“万妖穴中有若干小穴,每处小穴中皆有一只恶妖。小穴外设有封印,汝需消灭指定几处小穴中的恶妖方能解除该小穴封印,进而消灭穴中恶妖。”

“此处石壁所刻便是万妖穴中各穴的封印解除关系。”

“万妖穴中或有部分小穴未设封印,汝可以此作为突破口。”

“吾将根据石壁所示,将各穴消灭顺序给予汝,汝自珍重。”

输入
每个输入文件中一组数据。

第一行两个正整数N、M(1<=N<=1000,0<=M<=N*(N-1)),表示万妖穴中小穴的个数及封印解除关系的条数。

接下来M行,每行两个整数a、b,表示小穴b封印的解除依赖于消灭小穴a中的恶妖。假设N处小穴的编号分别是0~N-1。数据保证a不等于b,且每组封印解除关系a b最多出现一次。

输出
如果能够消灭所有小穴,那么输出一行YES,并在第二行给出用空格隔开的N处小穴的消灭顺序(此处规定,总是消灭当前能消灭的编号最小的小穴);如果不能消灭所有小穴,那么输出一行NO,并在第二行给出无法解除封印的小穴个数。行末均不允许输出多余的空格。

样例输入和输出那里贴不了多个case(提交的程序会强行测试sample),所以直接放这里吧
input:

// case 1
3 3
0 1
0 2
2 1
// case 2
4 5
0 1
0 2
0 3
2 1
1 2

output:

// case 1
YES
0 2 1
// case 2
NO
2

程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const int MAXV = 1010;
int n, m, inDegree[MAXV];
vector<int> G[MAXV],Q;
int topologicalSort(){
int num = 0;
priority_queue<int,vector<int>,greater<int>> q;
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.push(i);//入度为0入队列
}
}
while (!q.empty()) {
int u = q.top();
Q.push_back(u);
q.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
inDegree[v]--;//入度减少
if (inDegree[v] == 0) {
q.push(v);//入度为0,加入队列
}
}
num++;
}
return num;//返回拓扑结点个数
}
int main(){
scanf("%d%d",&n, &m);
memset(inDegree, 0, sizeof(inDegree));//初始化
int u, v;
for (int i = 0 ; i < m; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
inDegree[v]++;//入度++
}
int topological = topologicalSort();
if (topological == n) {//封印解除!
printf("YES\n");
for (int i = 0; i < n; i++) {
printf("%d", Q[i]);
if (i < n - 1) {
printf(" ");
}
}
}else{
printf("NO\n%d\n", n - topological);
}
return 0;
}

题目中要求『此处规定,总是消灭当前能消灭的编号最小的小穴』
所以采用优先队列

1
priority_queue<int, vector<int>, greater<int>> q;

下面给出一组测试数据

1
2
3
4
5
6
7
8
9
10
11
12
13
//input

6 5
0 1
0 2
1 5
1 3
1 4

//output

YES
0 1 2 3 4 5