感谢peter学长在路上给予的启发,虽然没想出来怎么用拓扑排序做出来
@Peter_5
//该题图的条件:只有小的点指向大的点,即1->2 2->5 3->4
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
数据结构区
const int N=10010;
int n,m;//点数,边数
int g[N][N];//邻接矩阵,因为还不是很熟练邻接表,只能牺牲电脑内存了
int f[N];//不走回头路
int cnt;//计数器
void dfs(int a)/
{
if(a==n)//起点终点相遇
{
cnt++;//计数器
}
for(int j=2;j<=n;j++)//遍历下一个可能的点,1就是我们本身
{
if(g[a][j]==1&&f[j]==0)//先判断有路可走,在判断是否已经走过
{
f[j]=1;
dfs(j);
f[j]=0;
}
}
}
int main()
{
cin>>n>>m;
//添加边操作
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=1;
}
dfs(1);
cout<<cnt<<endl;
return 0;
}
//最后测试,因为是单向图,不可能有回去的可能所以,可以不用判断是否经过,因为不会经过走过的点