C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 112ms, 内存消耗: 12824K, 提交时间: 2023-05-01 10:20:05

#include <iostream>
#include <vector>
#include <queue>

const int N = 1e5 + 10;
const int P = 98319;
int dp[N];

std::vector<int> redge[N];
int s, t;

int dfs(int u) {
    if (dp[u] != -1) return dp[u];
    int &res = dp[u] = 0;
    if (redge[u].empty()) return res = int(u == s);
    for (int v : redge[u]) {
        res = (res + dfs(v)) % P;
    }
    return res;
}

int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);

    int n, m;
    std::cin >> n >> m >> s >> t;

    while (m--) {
        int u, v;
        std::cin >> u >> v;
        redge[v].push_back(u);
    }
    std::fill(dp + 1, dp + n + 1, -1);

    int res = dfs(t);

    if (dp[s] != -1) std::cout << res << '\n';
    else std::cout << "TAT\n";

    return 0;
}

C++(clang++11) 解法, 执行用时: 156ms, 内存消耗: 13876K, 提交时间: 2021-03-24 18:56:37

#include<bits/stdc++.h>
using namespace std;
#define mod 98319
#define maxn 100010
int vis[maxn],dp[maxn],n,m,u,v,st,ed;
bool flag;
struct Node
{
	int id,num;
};
vector<int>Q[maxn];
int DFS(int pos)
{
	if(pos==ed) return flag=1;
	if(vis[pos]==-1) return dp[pos];
	int ans=0;
	for(int i=0;i<Q[pos].size();i++)
	{
		ans=(ans+DFS(Q[pos][i]))%mod;
	}
	vis[pos]=-1;
	return dp[pos]=ans;
}
int main()
{
	int ans;
	while(~scanf("%d%d%d%d",&n,&m,&st,&ed))
	{
		flag=0;
		memset(vis,0,sizeof(vis));
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
		Q[i].clear();
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			Q[u].push_back(v);
		}
		ans=DFS(st);
		if(flag==0)
		cout<<"TAT"<<endl;
		else
		cout<<ans<<endl;
	}
	return 0;
}