该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

完善程序题

下一个全排列

输入一个正数 $n$ ($2 \le n \le 10^6$)，以及-个长度为 $n$ 的排列、规定 ($1,2,3,4,\cdots,n$) 是第 $1$ 个排列, ($n,n-1,\cdots,1$) 是最后一个排列。

根据这 $n$ 个数组成的排列，输出下一个排列，每一个数后输出一个空格: 若这 $n$ 个数已经是最后一个排列，输出 No Next Permuation。

5
1 2 5 4 3

1 3 2 4 5

程序

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, num, mid, t, a[10000001], b[1000001];
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  int i = n;
  while (i > 1) {
    if (__1___) {
      num++;
      b[num] = a[i];
    }
    else {
      num++;
      b[num] = a[i];
      num++;
      ___2___;
      mid = i - 2;
      break;
    }
    i--;
  }
  if (i == 1) ____3____;
  else {
    for (int i = 1; i <= num - 1; i++)
      if (____4____) {
        t = b[i];
        b[i] = b[num];
        b[num] = t;
        break;
      }
    for (int i = 1; i <= mid; i++) cout << a[i] << " ";
    cout << b[num] << " ";
    for (int i = 1; i <= num - 1; i++) ___5___;
    cout << endl;
  }

34. (1) 处应该填写( )。

{{ select(34) }}

• a[i] < a[i-1]
• a[i+1] < a[i]
• a[i] > a[i-1]
• a[i+1] > a[i]

35. (2) 处应该填写( )。

{{ select(35) }}

• b[num]=a[i-2]
• b[num+1]=a[i-1]
• b[num+1]=a[i]
• b[num]=a[i-1]

36. (3) 处应该填写( )。

{{ select(36) }}

• num++
• mid=0
• mid--
• cout<<"No next Permuation"

37. (4) 处应该填写( )。

{{ select(37) }}

• b[i] > b[mid]
• b[i] < b[mid]
• b[i] < b[num]
• b[i] > b[num]

38. (5) 处应该填写( )。

{{ select(38) }}

• cout << b[i+1] <<" "
• cout << b[num-1] <<" "
• cout << b[i-1] <<" "
• cout << b[i] << " "

拓扑排序

给出一张 $n$ 个节点 $m$ 条边的有向图，求出该图的一个拓扑排序，若无拓扑排序输出 $-1$。

输入:

第一行两个正整数 $n,m$ 表示点数与边数。接下来 $m$ 行，每行两个正整数 $x,y$ 表示节点 $x$ 到节点 $y$ 之间有一条有向边。

输出:

一个拓扑序，按拓扑序输出点的编号。若拓扑序不唯一，输出任意一个均可。若无拓扑序，输出 $-1$。

关于拓扑序的例子，如学校里有 $A,B,C，D$ 四门课程，要求课程 $B,C$ 必须在学习课程 $A$ 之后才能学习，课程 $D$ 必须在学习课程 $B,C$ 之后学习。则序列 $ABCD$ 与序列 $ACBD$ 均是合理的拓扑序，而序列 $ABDC$ 与序列 $BACD$ 等均不是拓扑序。即在安排某课程时，其前置课程必须全部学习完毕。

试补全程序。

#include <algorithm>
#include <cstdio>
#include <vector>
#define N 200020
using namespace std;
int n, m;
vector<int> G[N];
int q[N], hd, tl;
int du[N];
int ans[N], tot;
void topo() {
  hd = 1, tl = 0;
  for (int i = 1; i <= n; i++) if (__1__) q[++tl] = i;
  
  while (hd <= tl) {
    int u = q[hd++];
    ans[++tot] = u;
    for (int i = 0; ____2___; i++) {
      int v = G[u][v];
      du[v]--;
      if (!du[v]) ___3___
    }
  }
  if (tot != n) puts("-1");
  else {
    for (int i = 1; i <= n; i++) {
      printf("%d", ans[i]);
    }
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    __4__;
    __5__;
  }
  topo();
}

39. (1) 处应该填写( )。

{{ select(39) }}

• du[i]
• q[i]
• hd <= tl
• !du[i]

40. (2) 处应该填写( )。

{{ select(40) }}

• i <= n
• i < n
• i < G[u].size()
• i <= G[u].size()

41. (3) 处应该填写( )。

{{ select(41) }}

• q[++tl] = v
• q[tl++] = v
• q[++hd] = v
• q[hd++] = v

42. (4) 处应该填写( )。

{{ select(42) }}

• G[y].push_back(x)
• G[x].push_back(y)
• G[x].push(y)
• G[y].push(x)

43. (5) 处应该填写( )。

{{ select(43) }}

• G[y].push_back(x)
• G[y].push(x)
• du[y]++
• du[x]++