L3-025 那就别担心了 (30 分)

题目描述：

有向无环图，起点x,终点y，问起点到终点有多少条路径，问是不是从x出发的所有路径都会指向一个无法往下走的点，即y

思路：

有向无环图，第一反应就是拓扑排序，但是怎么写都过不去，因为无法确定到底是不是"逻辑自洽"

正解：记忆化搜索

直接爆搜求路径，初始化是给num[y] = 1,然后去dfs(x),相当于倒着推，这样我们只需要判断是否存在某些点来过，且num ==0

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y;

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
inline void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int du[MAX];
int num[MAX];
bool vis[MAX];
int dfs(int u){
    if(num[u])return num[u];
    vis[u] = 1;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        num[u] += dfs(v);
    }
    return num[u];
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> x >> y;
        add(x, y);
        ++du[x];
    }
    cin >> x >> y;
    num[y] = 1;
    cout << dfs(x) << " ";
    for(int i = 1; i <= n; ++i){
        if(vis[i] && num[i] == 0){
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}


int main(){
    io;
    work();
    return 0;
}