Skip to content

L3-025 那就别担心了

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题，其实都不用担心。

ziqia.jpg

博主将这种逻辑推演称为“逻辑自洽”，即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题（开玩笑的，千万别以为这是真正的逻辑自洽的定义……）。现给定一个更为复杂的逻辑推理图，本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的，以及存在多少种不同的推理路径。例如上图，从“你遇到难题了吗？”到“那就别担心了”就是一种“逻辑自洽”的推理，一共有 3 条不同的推理路径。

输入格式

输入首先在一行中给出两个正整数 N（1 < N \le 500）和 M，分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。

接下来 M 行，每行给出一对命题之间的推理关系，即两个命题的编号 S1 S2，表示可以从 S1 推出 S2。题目保证任意两命题之间只存在最多一种推理关系，且任一命题不能循环自证（即从该命题出发推出该命题自己）。

最后一行给出待检验的两个命题的编号 A B。

输出格式

在一行中首先输出从 A 到 B 有多少种不同的推理路径，然后输出 Yes 如果推理是“逻辑自洽”的，或 No 如果不是。

题目保证输出数据不超过 10^9。

输入样例 1 

7 8
7 6
7 4
6 5
4 1
5 2
5 3
2 1
3 1
7 1

输出样例 1 

3 Yes

输入样例 2 

7 8
7 6
7 4
6 5
4 1
5 2
5 3
6 1
3 1
7 1

输出样例 2 

3 No

Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e2 + 10;
int n, m, st, ed, in[N], out[N], vis[N];
ll f[N];

vector<vector<int>> G;

void bfs(int st) {
    queue<int> que;
    que.push(st);
    vis[st] = 1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto &v : G[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                que.push(v);
            }
        }
    }
}

void topo(int st) {
    queue<int> que;
    que.push(st);
    f[st] = 1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto &v : G[u]) {
            f[v] += f[u];
            if (--in[v] == 0) {
                que.push(v);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    G.clear();
    G.resize(n + 1);
    memset(vis, 0, sizeof vis);
    memset(f, 0, sizeof f);
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    scanf("%d%d", &st, &ed);
    bfs(st);
    for (int u = 1; u <= n; ++u) {
        for (auto &v : G[u]) {
            if (vis[u] && vis[v]) {
                ++out[u];
                ++in[v];
            }
        }
    }
    int ok = 0;
    for (int i = 1; i <= n; ++i) {
        if (vis[i] && out[i] == 0) {
            ++ok;
        }
    }
    topo(st);
    cout << f[ed] << ' ' << ((f[ed] > 0 && ok == 1) ? "Yes" : "No") << endl;
    return 0;
}
Last update: May 4, 2022
Back to top