洛谷P2419 [USACO08JAN]Cow Contest S 题解 DAG上的简单搜索

题目链接:https://www.luogu.com.cn/problem/P2419

解题思路:

本题其实是求解一类 “关键点”(这里指的关键点是所有点和它之间都能够达到的那些点),我是用dfs搜了 \(n\) 边,因为是 DAG ,所以时间复杂度为 \(O(n^2)\)。

但是虽然题面里说保证是 DAG,但是数据好像没有完全保证的样子。所以在 dfs 函数的开头加了一句记忆化操作。

示例程序:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
vector<int> g[maxn];
int n, m, cnt;
bool ok[maxn][maxn];

// 判断是否存在一条从x到u的路径
void dfs(int x, int u) {
    if (ok[x][u]) return; // 不加这句话超时了6组数据,说明数据有问题,不能保证是DAG
    ok[x][u] = true;
    for (auto v : g[u])
        dfs(x, v);
}

// 判断每个点是否都可达x或x可达,如果是的话则x就是关键点
bool check(int x) {
    for (int i = 1; i <= n; i ++)
        if (!ok[x][i] && !ok[i][x])
            return false;
    return true;
}

int main() {
    cin >> n >> m;
    while (m --) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }
    for (int i = 1; i <= n; i ++) dfs(i, i);
    for (int i = 1; i <= n; i ++)
        if (check(i))
            cnt ++;
    cout << cnt << endl;
    return 0;
}
上一篇:Uniapp综合手册


下一篇:刷着玩-LeetCode20天算法-35. 搜索插入位置