题解：P14615 [2019 KAIST RUN Fall] Capital

zhangshiyan · 2025-11-28 09:24:16 · 题解

题解：P14615 [2019 KAIST RUN Fall] Capital

思路

题目中说所有在该道路上的人都从 A_i 单向前往 B_i，由因为人们从首都城市前往其他城市，说明 B_i 一定不可能为 S 首都城市。

所以，我们便可以对每一个 B_i 统计一个入度 in_{B_i}。

统计完之后，如果城市 i 的 in_i 为 0，即城市 i 没有入度，那么说明城市 i 可以为 S 首都城市。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const ll N = 500;

bool in[N + 5];

int main()
{
    ll n = read(), m = read();
    for (ll i = 1; i <= m; i++)
    {
        ll a = read(), b = read();
        in[b] = 1;
    }
    vector<ll> ans;
    for (ll i = 1; i <= n; i++)
    {
        if (!in[i])
        {
            ans.push_back(i);
        }
    }
    cout << ans.size() << endl;
    for (ll i : ans)
    {
        cout << i << " ";
    }
    return 0;
}