OJ题号:BZOJ4562、洛谷3183
思路:记忆化搜索。
本体可以转化成“求有向图中入度为0的结点到出度为0的结点的路径数”。
每次加边时记录每个结点的入度和出度,然后从入度为0的结点开始搜索,搜到出度为0的结点。
搜索到越底层,重复的路径越多,所以就要用记忆化的思想,将每个结点出发的路径个数记录下来,第二次搜到时直接调用。
#include<cstdio>
#include<vector>
const int N=;
std::vector<int> e[N];
int in_degree[N]={};
void add_edge(const int a,const int b) {
e[a].push_back(b);
in_degree[b]++;
}
bool isroot(const int x) {
return !in_degree[x];
}
bool isleaf(const int x) {
return !e[x].size();
}
int f[N]={};
int dfs(const int x) {
if(f[x]) return f[x];
if(isleaf(x)) return f[x]=;
int ans=;
for(int i=;i<(int)e[x].size();i++) {
ans+=dfs(e[x][i]);
}
return f[x]=ans;
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++) {
int a,b;
scanf("%d%d",&a,&b);
add_edge(a,b);
}
int ans=;
for(int i=;i<=n;i++) {
if(isroot(i)&&!isleaf(i)) ans+=dfs(i);
}
printf("%d\n",ans);
return ;
}