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

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int nxt,to;
}edge[400050];
pair<int,int> pa[400050];
int head[100050],idx = 0, in[100050], out[100050];
void add(int st,int ed) {
    idx++;
    edge[idx].nxt = head[st];
    head[st] = idx;
    edge[idx].to = ed;
}
int n, m, u, v;
int sta[100050], idx_st, nex[100050];
void dfs(int st) {
    if (!st)return;
    if (! nex[st]) {
        nex[st] = head[st];
        dfs(edge[nex[st]].to);
    }
    for (int i = edge[nex[st]].nxt; i; i = edge[nex[st]].nxt) {
        nex[st] = i;
        dfs(edge[i].to);
    }
    sta[idx_st++] = st;
}
int main()
{
    int flag = 1, cnt_in = 0, cnt_out = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        pa[i].first = u;
        pa[i].second = v;
        in[v]++;
        out[u]++;
    }
    sort(pa, pa + m,greater<>{});
    for (int i = 0; i < m; i++) {
        add(pa[i].first,pa[i].second);
    }
    for (int i = 1; i <= n; i++) {
        if (in[i] != out[i]) {
            if (in[i] - out[i] == 1) cnt_in++;
            else if (out[i] - in[i] == 1) cnt_out++, flag = i; //46行
            else return cout << "No\n", 0;
        }
    }
    if (!(cnt_in == 0 && cnt_out == 0 || cnt_in == 1 && cnt_out == 1)) return cout << "No\n", 0;
    dfs(flag);
    for (int i = idx_st - 1; i >= 0; i--) {
        cout << sta[i] << ' ';
    }
    return 0;
}

1<=n,u,v<=$10^5$,1<=m<=$4*10^5$

判断题

1. 当输入为 5 0时，程序会出错 {{ select(1) }}

• 正确
• 错误

2. 对于不输出No的输入，idx == n {{ select(2) }}

• 正确
• 错误

3. 将46行的flag = i移到上一行的分号前，对于不输出No的输入，idx不变 {{ select(3) }}

• 正确
• 错误

4. 将dfs()改为

void dfs(int st) {
    for (int i = edge[st].nxt; i; i = edge[i].nxt) {
    	if(vis[i])continue;
    	vis[i] = 1;
        dfs(edge[i].to);
    }
    sta[idx_st++] = st;
}

对于任何合法输入，结果不变(2.5分) {{ select(4) }}

• 正确
• 错误

选择题

5. 该程序的时间复杂度为 {{ select(5) }}

• O(m+n)

• O ($n^2 + m$)

• O ($m^2 + n$)

• O($2^{m+n}$)

6. 当输入为

4 6
1 3
2 1
4 2
3 3
1 2
3 4

时，输出为() {{ select(6) }}

• 1 2 1 3 3 4 2

• 2 4 3 3 1 2 1

• 3 3 2 4 1 2 1

• No

完善程序（单选题，每小题 3 分）

题目描述

对于一个城市来说，排水系统是极其重要的一个部分。

有一天，小 C 拿到了某座城市排水系统的设计图。排水系统由 $n$ 个排水结点（它们从 $1 \sim n$ 编号）和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水（简称为该结点的汇集管道），也有若干个管道向其他的排水结点排出污水（简称为该结点的排出管道）。

排水系统的结点中有 $m$ 个污水接收口，它们的编号分别为 $1, 2, \ldots , m$，污水只能从这些接收口流入排水系统，并且这些结点没有汇集管道。排水系统中还有若干个最终排水口，它们将污水运送到污水处理厂，没有排出管道的结点便可视为一个最终排水口。

现在各个污水接收口分别都接收了 $1$ 吨污水，污水进入每个结点后，会均等地从当前结点的每一个排出管道流向其他排水结点，而最终排水口将把污水排出系统。

现在小 C 想知道，在该城市的排水系统中，每个最终排水口会排出多少污水。该城市的排水系统设计科学，管道不会形成回路，即不会发生污水形成环流的情况。

输入格式

第一个两个用单个空格分隔的整数 $n, m$。分别表示排水结点数与接收口数量。
接下来 $n$ 行，第 $i$ 行用于描述结点 $i$ 的所有排出管道。其中每行第一个整数 $d_i$ 表示其排出管道的数量，接下来 $d_i$ 个用单个空格分隔的整数 $a_1, a_2, \ldots , a_{d_i}$ 依次表示管道的目标排水结点。
保证不会出现两条起始结点与目标结点均相同的管道。

输出格式

输出若干行，按照编号从小到大的顺序，给出每个最终排水口排出的污水体积。其中体积使用分数形式进行输出，即每行输出两个用单个空格分隔的整数 $p$，$q$，表示排出的污水体积为 $\frac{p}{q}$。要求 $p$ 与 $q$ 互素，$q = 1$ 时也需要输出 $q$。

样例输入

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

样例输出

1 3
2 3

#include<bits/stdc++.h>
using namespace std;
#define ll __int128
#define pll pair<unsigned __int128,unsigned __int128>
#define pii pair<int,int>
#define N 1000050
pll dp[N];
ll gcd(ll a, ll b) {__1__}
string out(ll a){
    string s;
    while (a) {
        s += (a % 10 + '0');
        a /= 10;
    }
    reverse(s.begin(), s.end());
    return s;
}
pll add(pll a, pll b) {
    if (b.second == 0) return a;
    if (a.second == 0) return b;
    ll tmp = a.second * b.second / gcd(a.second,b.second);
    pll tmp_;
    tmp_.first = __2__;
    tmp_.second = tmp;
    tmp = gcd(tmp_.first,tmp_.second);
    tmp_.first /= tmp;
    tmp_.second /= tmp;
    return tmp_;
}
pll div(pll a,ll b) {
    ll tmp = gcd(a.first,b);
    a.first /= tmp;
    b /= tmp;
    a.second *= b;
    return a;
}
pii ro[N];
int head[N], idx;
void Add(int st, int ed){
    idx++;
    ro[idx] = make_pair(ed,head[st]);
    head[st] = idx;
}
int n, m, d[N], a, in[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)__3__;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        for (int j = 1; j <= d[i]; j++) {
            cin >> a;
            Add(i, a);
            in[a]++;
        }
    }
    queue<int>qu;
    for (int i = 1; i <= n; i++) {
        if (!in[i]) {
            qu.push(i);
        }
    }
    while (!qu.empty()) {
        int r = qu.front();qu.pop();
        __4__;
        for (int i = head[r]; i; i = ro[i].second) {
            in[ro[i].first]--;
            __5__;
            if (!in[ro[i].first]) {
                qu.push(ro[i].first);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!d[i]) {
            ll tmp = gcd(dp[i].first, dp[i].second);
            dp[i].first /= tmp;
            dp[i].second /= tmp;
            cout << out(dp[i].first) << ' ' << out(dp[i].second) << endl;
        }
    }
    return 0;
}

1.1处应该填写（） {{ select(7) }}

• return b ? gcd(b, a % b) : a;

• return b ? a : gcd(b, a % b);

• return b == 0 ? gcd(b, a % b) : a;

• return a == 0 ? gcd(a, b % a) : b;

2.2处应该填写（） {{ select(8) }}

• a.first * tmp / a.second + b.first * tmp / b.second
• (a.first * tmp + b.first * tmp) / a.second / b.second
• a.first * (tmp / a.second) + b.first * (tmp / b.second)
• (a.first+ b.first) * tmp / a.second / b.second

3.3处应该填写（） {{ select(9) }}

• dp[i].first = 1, dp[i].second = 2
• dp[i].first = dp[i].second = 114514
• dp[i].first = 2, dp[i].second = 1
• dp[i].first = dp[i].second = 0x7fffffffffff

4.4处应该填写（） {{ select(10) }}

• dp[r] = div(dp[r],d[r] - 1);
• dp[r] = div(dp[r],d[r]);
• if(d[r]) dp[r] = div(dp[r],d[r]);
• if(d[r]) dp[r] = div(dp[r],d[r] - 1);

5.5处应该填写（） {{ select(11) }}

• dp[r] = add(dp[r],dp[ro[i].first]);
• dp[ro[i].first] = add(add(dp[r],dp[r]), dp[ro[i].first]);
• dp[r] = add(add(dp[ro[i].first],dp[r]), dp[ro[i].first]);
• dp[ro[i].first] = add(dp[r],dp[ro[i].first]);