那就别担心了 PTA L3
常规dfs
比赛的时候题意没搞清楚，写了个dfs结果拿了18分就寄了。大概就是问起点到终点一共有几个不同走法，然后问是否从起点开始的所有路径都只能通往终点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<bits/stdc++.h>
using namespace std;
const int N=550;
int cnt[N],vis[N];
vector<int>t[N];
int dfs(int u){
vis[u]=1;
if(cnt[u])return cnt[u];
for(auto v:t[u]){
cnt[u]+=dfs(v);
}
return cnt[u];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
t[u].push_back(v);
}
int st,ed;
cin>>st>>ed;
cnt[ed]=1;
dfs(st);
cout<<cnt[st]<<' ';
for(int i=1;i<=n;i++){
if((vis[i]&&cnt[i]==0)){
cout<<"No";
return 0;
}
}
cout<<"Yes";
return 0;
}
|