题解：P14615 [2019 KAIST RUN Fall] Capital

· · 题解

题解：P14615 [2019 KAIST RUN Fall] Capital

可以观察到，“首都”的要求是人们必须从这个点离开，去到别的点，也就是不能有其他的边指向这个点，即入度为 0。

因此，可以得到：
形式化题意：在给定的点数为 N，边数为 M 的简单有向图中，找出若干个入度为 0 的点。

建好图，依次把每个点作为“首都”开始 DFS/BFS，所有可以走到的点全部标为“不可成为首都”，最后枚举一遍所有点，把没有带标记的点记录输出即可。

因为每一条路的长度你都可以自己设定，所以不用管题目里“人们尝试沿最短路径移动”这一句话，关注图的连通性就行。

时间复杂度为 O(N(N + M))，在 N = 500 时约为 2.5 \times 10^5 次运算，不用怎么优化，完全可过。

示例代码如下：


#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n, m, visited[510], can_vis[510], ansls[510], idx;
vector<int> a[510];

void dfs(int p, int start){
    if(visited[p])
        return;
    if(p != start)
        can_vis[p] = 1; // 如果可以走到，并且不是初始点，则这个点不能成为首都
    visited[p] = 1;
    for(int i = 0; i < a[p].size(); i++)
        dfs(a[p][i], start);
    return;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
    } // 建图

    for(int i = 1; i <= n; i++){
        memset(visited, 0, sizeof visited);
        dfs(i, i);
    } // 遍历

    for(int i = 1; i <= n; i++)
        if(can_vis[i] == 0){
            ansls[idx] = i;
            idx++;
        } // 统计答案

    cout << idx << endl;
    for(int i = 0; i < idx; i++)
        cout << ansls[i] << endl; // 输出
}
求赞 qwq